All information is provided. And it is based on Branch and bound (B&B), Dijkstra's algorithm..

Table 1 shows the transition time of 13 flight legs. The airline now has to determine how to make a route that can minimize the transition time from Sto S'.

(a) Please explain whether you would suggest the airline to use B&B or Dijkstra Algorithm.

(b) Please also explain by wording how to solve it.

Table 1. Transition time of 13 flight legs.

Direction Transition time (Hours)

1. S to A   5

2. S to B   7

3. S to C 5

4. A to B 3

5. A to D 1

6. A to E 7

7. B to C 1

8. B to S' 5

9. C to F 2

10. D to S' 18

11. E to S' 13

12. F to E 3

13. F to S' 19

Answer:

Branch and bound (B&B) is an algorithm design for discrete and combinatorial optimization problems, as well as mathematical optimization. The algorithm explores branches of the tree diagram, which represent subsets of the solution set. However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.

Dijkstra's algorithm is an algorithm that is used to solve the shortest distance problem.

Since B&B method is a highly complex one and leads to the generation of errors; sometimes of the worst type; hence, we would be using Dijkstra’s algorithm for solving the transition time problem of the airline.

Procedure to solve the transition time problem of the airline through Dijkstra's algorithm:

1. Convert the table into the network diagram.

2. Identify the shortest time between the nodes.

3. Keep on identifying the further shortest paths between two nodes while connecting node through nodes until the destination is arrived on.

Hence, the shortest path is [ S – A – B – S’] with the transition time being (5 + 3 + 5 = 15 Hours)

PFA