Algorithms of Best Paths
Yonghui Wu, Jiande Wang · 2016
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.