next up previous
Next: 7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm Up: 7. Directed Graphs Previous: 7.1.1 Data Structures for Graph Representation

7.2 Shortest Paths Problem

Given : A digraph G = (V, E) in which each arc has a non-negative cost and one vertex is designated as the source.
Problem : To determine the cost of the shortest path from the source to every other vertex in V (where the length of a path is just the sum of the costs of the arcs on the path).