Task 2 (Shortest Path Problem & Dijkstra-Algorithm) A A B CDEFG - 2 T 9 9...

  

Transcribed Image Text:

Task 2 (Shortest Path Problem & Dijkstra-Algorithm) A A B CDEFG - 2 T 9 9 F BODBE 1 2 0 1 G 9 1019 1 0 2 2 0 1 1 0 20 Points Table 2: Arc traversing costs in the shortest path problem There is a transportation network formed by the seven nodes A, B, C., G. We have no information about the locations of the nodes but we know which connections between which pairs of knots are available. In addition, we are informed about the costs to use these connections. Tab. summarizes these information. The sign "-" indicates that there is no direct connection (are) available. a) Use the Dijkstra-Algorithm to determine a least cost path through the network which originates from node A and terminates in node G. You have to use the tabular representation of the Dijkstra-Algorithm. Fill out the following Tab. Iteration permanently labeled node current label values (permanent values are marked by) 1 2 3 4 5 6 7 A B C D E F G Table 3: Tabular representation of the Dijkstra-Algorithm b) What is the shortest path in this situation? Give the found node sequence. The shortest path is c) What is the length of the shortest path? The shortest path length is = Task 2 (Shortest Path Problem & Dijkstra-Algorithm) A A B CDEFG - 2 T 9 9 F BODBE 1 2 0 1 G 9 1019 1 0 2 2 0 1 1 0 20 Points Table 2: Arc traversing costs in the shortest path problem There is a transportation network formed by the seven nodes A, B, C., G. We have no information about the locations of the nodes but we know which connections between which pairs of knots are available. In addition, we are informed about the costs to use these connections. Tab. summarizes these information. The sign "-" indicates that there is no direct connection (are) available. a) Use the Dijkstra-Algorithm to determine a least cost path through the network which originates from node A and terminates in node G. You have to use the tabular representation of the Dijkstra-Algorithm. Fill out the following Tab. Iteration permanently labeled node current label values (permanent values are marked by) 1 2 3 4 5 6 7 A B C D E F G Table 3: Tabular representation of the Dijkstra-Algorithm b) What is the shortest path in this situation? Give the found node sequence. The shortest path is c) What is the length of the shortest path? The shortest path length is =