ABSTRACT
Given a weighted, directed graph G = (V, E), each edge is with a real-valued weight. The weight of path P = (v0, v1, …, vk) is the sum of weights of its constituent edges:
w p w v vi i
( ) ( , )= −
The weight of the shortest path (longest path) from vertex u to vertex v is defined as follows:
δ( , ) min(max){ ( ) }u v w p u v p u
=
→ if there is a path from to v
∞
otherwise
The best path from vertex u to vertex v is defined as any path with weight w(p) = δ(u, v). In this chapter, three kinds of algorithms are introduced:
1. The Warshall algorithm is used to get the transitive closure for a graph. 2. The Floyd-Warshall algorithm is used to get all-pairs best paths in a graph. 3. The Dijkstra algorithm, Bellman-Ford algorithm, and shortest path faster algorithm (SPFA)
are used to get single-source shortest paths in a graph.
