English
Menu

Data Structures and Algorithms

In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?

  1. AS→A→C→T, length 8
  2. BS→B→A→C→T, length 7
  3. CS→B→C→T, length 9
Show answer and explanation

Answer: B. S→B→A→C→T, length 7

Dijkstra's algorithm repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors. From S (0), B is finalized at 1, and going through B gives A a distance of 1 + 2 = 3, shorter than the direct 4. Finalizing A (3) gives C 3 + 1 = 4 and T 3 + 6 = 9, and finalizing C (4) updates T to 4 + 3 = 7. The shortest path is therefore S→B→A→C→T with length 7. S→A→C→T (8) is longer because it takes S−A directly, and S→B→C→T (9) is longer because B−C has the large weight 5.

  • A. Going from S to A through B (1 + 2 = 3) is shorter than going directly (4).
  • B. Correct. S→B (1), B→A (2), A→C (1) and C→T (3) total 7.
  • C. B−C has a large weight of 5, so going through A is shorter.
Practice this topic Back to topic

Related calculators

Dijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagramSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. Which condition on the graph is required for Dijkstra's algorithm to find correct shortest paths?
  2. Tasks A to E have the ordering constraints “A before C”, “B before C”, “C before D”, “B before E” and “E before D”. Which order satisfies all the constraints (a result of topological sorting)?
  3. A function f(x, y) is defined as “if y is 0, return x; otherwise return f(y, x mod y)”. When f(84, 36) is called, what is the return value, and how many times is f called, including the first call?
  4. A function fib(n) for Fibonacci numbers is defined recursively as “if n is 1 or less, return n; otherwise return fib(n−1) + fib(n−2)”. When fib(5) is called, how many times is fib called, including the first call?
  5. You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which correctly relates the number of coins chosen by a greedy algorithm, which uses as many of the largest coin as possible first, to the minimum number of coins?