English
Menu

Data Structures and Algorithms

Which condition on the graph is required for Dijkstra's algorithm to find correct shortest paths?

  1. AThe graph has no cycles (paths that return to the same vertex)
  2. BThe edges have no direction
  3. CAll edge weights are 0 or greater
Show answer and explanation

Answer: C. All edge weights are 0 or greater

Dijkstra's algorithm finalizes the unfinalized vertex with the smallest distance. This relies on the assumption that going through other vertices can only increase a distance, never decrease it. With a negative edge, a distance can become shorter later through another route; for example, in a directed graph with S→A 2, S→B 3 and B→A −2, A is finalized at 2 before the path S→B→A of length 1 is found. When negative weights exist, the Bellman-Ford algorithm or similar methods are used. Dijkstra's algorithm works with cycles and with directed edges as long as all weights are 0 or greater.

  • A. It works correctly with cycles as long as the weights are 0 or greater; road networks are full of cycles.
  • B. It also works on directed graphs.
  • C. Correct. With negative weights, a finalized distance can later turn out to be 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. 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)?
  2. 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?
  3. 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?
  4. 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?
  5. A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?