Critical Path
Logical Reasoning



1. Introduction

A critical path is an analytical tool used to manage projects involving a large number of activities and multiple resources. It is a sequence of activities undertaken to solve any problem or to complete a project such that a certain parameter is optimized.

For instance, consider that a project manager has to complete a project that has been assigned to him. The parameters that he has to take into consideration are time, man power and office resources. Depending upon the parameter that is to be optimized, the manager has to accordingly chalk out a project schedule.

So, if the requirement is to complete the project in minimal time, then the manager has to assign maximum human and office resources. If the manager has been assigned a fixed number of people, then time taken for completion of the project would increase accordingly.

To understand this better, we will take a real life example. Suppose there are three ways of travelling from Mumbai to Delhi: Road, Rail and Air. The critical path in this case is the one that satisfies certain minimum criteria. For instance, if the cost has to be minimized, then the preferred mode of travel should be Rail. If time has to be minimized, then it should be Air. Thus, critical path depends solely on the parameter that is being optimized.

Image for Critical Path, Logical Reasoning:39-1

The typical critical path question set consists of a graph or tabular data that gives information about nodes, paths and their associated parameters followed by questions regarding optimization. In the above example, the nodes are the cities Mumbai and Delhi; paths are the three routes, while the parameters are time of travel and cost of travel.

Let us introduce two more nodes as intermediate cities. Every route has a cost associated with it which can be considered as the cost of travel. Let us determine the critical path from Mumbai to Delhi that minimizes the cost.

Image for Critical Path, Logical Reasoning:39-2

The different paths that exist from Mumbai to Delhi are:

  1. Mumbai – Bhopal – Delhi
  2. Mumbai – Bhopal – Ajmer – Delhi
  3. Mumbai – Ajmer – Delhi

Now, let us calculate the cost of travel along these paths. It is nothing but the addition of the costs associated with all the routes of a particular path.

This means that the first path (Mumbai – Bhopal – Delhi) has a total cost of (23 + 28) i.e. 51 units.

Similarly, the total costs for all the other paths are as follows.

  1. Mumbai – Bhopal – Ajmer – Delhi $\rightarrow$ 48 units
  2. Mumbai – Ajmer – Delhi $\rightarrow$ 52 units

The cost of the second path is minimized. Thus, the second path becomes the critical path for this problem.

There can also be parameters associated with each node. In our example, suppose there is some accommodation cost or halting time associated with each intermediate node i.e. Bhopal and Ajmer. In any case, the cost is denoted using the same units as the cost of the routes. While calculating the total cost of a path, simply add the node cost to the total cost of the routes joining the nodes. Let us look at the diagram below that has the node costs marked.

Image for Critical Path, Logical Reasoning:39-3

We now calculate the total costs for the three existing paths.

1. Mumbai – Bhopal – Delhi

Total cost = 23 + 12 + 28 = 63 units

2. Mumbai – Bhopal – Ajmer – Delhi

Total cost = 23 + 12 + 17 + 7 + 8 = 67 units

3. Mumbai – Ajmer – Delhi

Total cost = 44 + 7 + 8 = 59 units

It can be seen that with the additional node costs, the second path is no longer the critical path. The third path has the minimal cost and hence, is the critical path.

Top

2. Types of Critical Path Problems

Critical path problems are mainly of two types:


2.1. Diagram Based Problems

In such problems, the sequence of activities (or routes) is expressed in the form of a diagram, also known as a network. This diagram provides information not only on which activity is to be done first and which later, but also the time taken for each activity and the interdependency between multiple activities. For instance, a diagram may show that two cities on a map, A and B are connected by a one-directional arrow. This implies that one can go along this route only from A to B and not from B to A. On the other hand, if the arrow is bi-directional, one can travel in both the directions using this route.

Diagram based problems are of three main types. The first type has single questions based on a diagram, which is usually a network with nodes and paths between the nodes. One is required to find the number of ways in which one can visit all the nodes and return to the initial node using all paths only once, or some variation of this problem.

The second type involves a diagram of a network with nodes and paths, similar to that in the first part. However, each path has a parameter associated to it.

The third type has costs associated with each node in addition to the costs of the roads. Typically, the costs for the nodes are not given and we are required to find out those costs based on the given information.

The most common example for these types of problems is a network of nodes connected by roads. Vehicles travel on these roads and there is a cost associated with every road or both, the roads and the nodes. Some of the points to be taken into consideration while solving diagram based problems are as follows:

  • Before starting the problems, look at the questions carefully. Most questions can be solved on the basis of the original diagram only. However, if each question has separate conditions given, thereby necessitating rework as well as multiple calculations, it may be a good idea to draw a new diagram for each question.
  • For problems where only one parameter (cost, time, etc) is given, draw a table where the sum of that parameter for each route from the initial point to the final point is also calculated. If any of the question deals with a change in the value of that parameter on a particular road, draw a new table with the values recalculated (only if needed).
  • For problems where nodal parameters are also to be considered, denote all the unknown node costs by variables. After this, draw a table with all possible routes and calculate the total value of the parameter for each route in terms of the unknown variables.
  • Now, enforce the conditions given in the question. For example, you may be told that all the paths have equal cost. In this case, equate total costs for all paths. This will enable you to find the values of all variables and hence find the cost of travel through all nodes.

Example:

Two days (Thursday and Friday) are left for campaigning before a major election, and the city administration has received requests from five political parties for taking out their processions along the following routes.

Congress: A-C-D-E

BJP: A-B-D-E

SP: A-B-C-E

BSP: B-C-E

CPM: A-C-D

Street B-D cannot be used for a political procession on Thursday due to a religious procession. The district administration has a policy of not allowing more than one procession to pass along the same street on the same day. However, the administration must allow all parties to take out their procession during these two days.

Image for Critical Path, Logical Reasoning:39-4

Question 1:

Congress procession can be allowed:

(1) Only on Thursday.

(2) Only on Friday.

(3) On either day.

(4) Only if the religious procession is cancelled.

Solution:

$\because$ Route BD cannot be used on Thursday.

$\because$ BJP has to take out its procession on Friday.

$\because$ Route DE is common to BJP and Congress.

$\therefore$ Congress should take out its procession on Thursday.

$\because$ Route AB is common to SP and BJP.

$\therefore$ SP should take out its procession on Thursday.

$\therefore$ BSP and CPM have to take out their processions on Friday.

$\therefore$ Congress procession can be allowed only on Thursday.

Table below can be scrolled horizontally

Thursday Friday
Congress BJP
SP BSP
  CPM

Hence, option A is the correct choice.

Top

Question 2:

Which of the following is not true?

(1) Congress and SP can take out their processions on the same day.

(2) The CPM procession cannot be allowed on Thursday.

(3) The BJP procession can only take place on Friday.

(4) Congress and BSP can take out their processions on the same day.

Solution:

From the explanation given in the solution of the first question we get that,

Congress takes out a procession on Thursday and BSP on Friday.

$\therefore$ Only option D is not true.

Hence, option D is the correct choice.

Top

2.2. Tabulated Problems

A tabulated problem is a critical path problem in which all the data is already given in the form of a table. The nodes may be cities or activities or junctions and so on. The table provides information pertaining to the route or process between the nodes. Based on this information, we are required to identify the critical path between two specified nodes.

Some of the points to be taken into consideration while solving tabulated problems are as follows.

  • First, look at the questions given to determine the source and the destination. The source and destination may not be the first and the last node given in the table.
  • If no clear source or destination can be identified, go straight to the questions and treat them individually.
  • If the source and destination can be identified, draw a diagram depicting all the nodes as circles and draw all possible connections between the nodes.
  • From this diagram, note down all the possible paths between the source and destination.
  • Now, draw a second table. The first column of this table holds all the possible routes identified in the step above. In the remaining columns calculate the cumulative parameters for each route. However, this table may not always be required. Hence, look at the questions carefully before spending time on the second table.

Top

Example:

A thief has stolen 50,000 Euros in London and wants to get to Rome. He is not willing to spend more than 1% of money he has with him. Assume that he had no money before the theft. He has collected information about the flights between London and a number of other cities through which he can travel to reach Rome.

He knows how much it costs to go from one city to the other, how much time it takes and also the risk factor, which measures the probability that he will be caught on a particular route.

This information is summarized in the table below.

Table below can be scrolled horizontally

Route Cost (in Euros) Time (in hours) Risk factor
London – Paris 175 2 30
London – Brussels 350 3 25
London – Berlin 325 4 35
London – Rome 500 6 50
Paris – Berlin 200 1.5 15
Paris – Rome 275 3.5 20
Brussels – Berlin 150 1.5 10
Brussels – Paris 125 1 0
Brussels – Rome 200 2.75 20
Berlin – Rome 250 2 15

Analysis of the information

Initial budget of the thief = 50,000 Image for Critical Path, Logical Reasoning:39-5 0.01 = 500 Euros.

Since he is not willing to spend above this amount, he will go for any route with cost up to 500 Euros.

1. Preparation of a diagram: Source and destination have been mentioned explicitly in the problem i.e. London and Rome respectively. Hence, prepare a diagram showing all the possible routes connecting these two cities only.

We shall use short forms as follows: L, P, Br, Be and R for London, Paris, Brussels, Berlin and Rome respectively.

Our diagram looks like as given below.

Image for Critical Path, Logical Reasoning:39-6

2. The information about all the possible routes that the thief can take is summarized in the table below.

Table below can be scrolled horizontally

Possible Routes Total Cost(in Euros) Total Time(in hours) Total Risk Factor
L – P – R 450 5.5 50
L – P – Be – R 625 5.5 60
L – Br – P – R 750 7.5 45
L – Br – P – Be – R 925 7.5 55
L – Br – Be – R 750 6.5 50
L – Br – R 550 5.75 45
L – Be – R 575 6 50
L – R 500 6 50

Question 1:

If the thief disregards all other parameters and only looks at the cost of the journey between London and Rome, how many possible paths can he take?

(1) 0      (2) 1      (3) 2      (4) 3      (5) 4

Solution:

The thief does not want to spend more than 500 Euros. Hence, if only cost is to be considered, he goes for paths that cost less than or equal to 500 Euros.

From the table, only two routes L – P – R (450 Euros) and L – R (500 Euros) satisfy the criterion.

Hence, option 3 is the correct choice.

Top

Question 2:

The thief steals 10,000 more Euros after his initial theft of 50,000 Euros. However, the police get on his trail because of this second theft, and he has to reach Rome from London in less than 6 hours. How many different routes can he take?

(1) 2      (2) 3      (3) 4      (4) 5      (5) None of these

Solution:

The budget of the thief is now $60,000 \times 0.01 = 600$ Euros.

Now, consider routes where the total cost is not more than 600 Euros and the total time taken is less than 6 hours. From the table, only L – P – R and L – Br – R satisfy both these conditions.

Hence, option 1 is the correct choice.

Top

Question 3:

The thief receives a tip-off that the police have circulated a description of him to all the European airports. He therefore decides that money and time are not factors. The only parameter he needs to worry about is the Risk Factor. Any route with a Risk Factor of more than 50 is unacceptable.

How many different routes can he take in this case?

(1) 2      (2) 3      (3) 4      (4) 5      (5) 6

Solution:

Since the thief needs to travel by a route where the risk factor is not more than 50, consider all the routes where the risk factor is less than or equal to 50. From the table, 6 routes satisfy this condition.

Hence, he can use any one of 6 possible routes.

Hence, option 5 is the correct choice.

Top

Question 4:

An honest man finds the thief’s flight information and uses it to plan a journey of least time between London and Rome. To which city will he first travel based on his plan?

(1) Paris     (2) Brussels     (3) Berlin     (4) Rome      (5) Either (2) or (3)

Solution:

From the table, the two routes with the minimum travelling time are L – P – R and L – P – Be – R. In both these routes, the first stop after London is Paris. Thus, the honest man will first travel to Paris.

Hence, option 1 is the correct choice.

Top

3. Strategy Tips

  • In any problem, it is advisable to draw a diagram of the network so that all the possible paths from ‘start’ to ‘finish’ can be identified in the lowest possible time.
  • Try to depict as much information as possible on the diagram itself so as to avoid drawing tables. Also, by doing so, you do not need to look at multiple figures.
  • It is advisable to have a look at the questions before hand as the knowledge of the questions asked can help cut down on solving time since data that is not useful in answering any question can be discarded, thus simplifying the problem set.
  • Do not label the main diagram with total costs as the data given for different questions may be different. This may result in overwritten labels and unwanted confusion.
  • If the answer options contain number of routes i.e. 1, 2, 3 and so on, the problem may involve checking individual routes. These problems may generally be more time consuming. However, questions asking for number of routes that satisfy a certain condition may not take too much time as few routes may get eliminated.
  • If routes or paths are given in the options, verify only for those routes. But, you may need to verify for all the other routes if one of the answer options is ‘none of the above’.
  • A longer route in the options may not necessarily be costlier or more time-consuming. For instance, a route P-Q-R-S may be less time consuming than a route P-Q-S if the time taken to travel from Q to S directly is very large.
  • At times, the diagrams given are made complex unnecessarily by placing adjacent nodes at extremes and joining them haphazardly using overlapping routes. If the diagram looks complex, try simplifying it by redrawing it.
  • The source and the destination nodes for a problem may differ across questions, so avoid plotting down all possible paths for all nodes for a particular question.
  • In case, each question has a different condition, one can draw separate tables for each question or can draw one table and keep each cell relatively large in size. Now, fill in the data for one question at one of the corners of the cell, solve the question and cancel out the data. Use this approach for each question. However, use this approach if and only if you are comfortable working with a lot of data in one table. This approach is preferable in a paper-pencil based test, where there may not be enough space to draw multiple tables or figures.

Top

Hide
 
 
 

Number formats

Decimals
Lofoya.com   2016

You may drag this calculator