DataStructure Shortest Path Problem
Shortest Path Problem
Find the minimum weight in all the paths between 2 vertexes. This is called the Shortest Path. The start point is called Source Vertex the end point is called Destination Vertex.
Problems
- Single-source Shortest Paths
- (directed) Unweighted graph
- (directed) Weighted graph
- Multi-Source Shortest Paths
Single Source Shortest Path Algorithm for Unweighted Graphs
Find the shortest path in Non-decreasing order. It is very similar to BFS!
1 | void Unweighted(Vertex S){ |
Single Source Shortest Path Algorithm for Weighted Graphs
There is an interesting thing called negative-cost cycle. In this loop, the best way is to travel endlessly in this cycle.
Dijkstra Algorithm
- S = {source s, vertexes that their shortest paths have already been found}
- For any vertex that is not in S, dist[v] is the shortest path from s to v, but this path only consists the vertexes in S.
- This algorithm requires the Non-decreasing order of generating paths.
- In this case, the shortest path must be only consisted of vertexes in S.
- Each time choose a vertex that has the least distance.
- When appending S, this action may affect another vertex (w) dist[w]!
- In this case, w is connected directly to v and!
- dist[w] = min{dist[w], dist[v] + weight}
1 | void Dijkstra(Vertex s) { |
There are several ways of getting V!
- Scan uncollected set, find the one with the minimum distance. This method is very suitable for Dense Graph (graph with a lot of edges).
- Store the distance of v in a MinHeap
Multi-source Shortest Paths Algorithms
- Use the Single-source Shortest Path Algorithm on every vertex. This method is suitable for Sparse graph.
- Floyd Algorithm
Floyd Algorithm
The final shortest path is given by
1 | void Floyd(){ |