Shortest Path Algorithms

Shortest path algorithms are fundamental tools in computer science and graph theory, used to find a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. These algorithms have wide-ranging applications, from GPS navigation and network routing to resource allocation and logistics.

1. Introduction to Shortest Path Problems

A weighted graph $G = (V, E, w)$ is a graph where each edge $(u, v) \in E$ has an associated numerical weight or cost $w(u, v)$ . This weight can represent distance, time, monetary cost, or any other quantifiable metric. The length of a path $P = \langle v_0, v_1, \dots, v_k \rangle$ in a weighted graph is the sum of the weights of its constituent edges:

$L(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})$

The shortest path problem aims to find a path between two specified vertices whose length is minimized. There are two primary variants of this problem:

Single-Source Shortest Path (SSSP): Find the shortest paths from a single designated source vertex $s$ to all other vertices in the graph.
All-Pairs Shortest Path (APSP): Find the shortest paths between every pair of vertices in the graph.

2. Single-Source Shortest Path (SSSP): Dijkstra's Algorithm

Dijkstra's Algorithm is a greedy algorithm that solves the Single-Source Shortest Path problem for a graph with non-negative edge weights. It produces a shortest path tree from the source vertex to all other reachable vertices.

2.1 Principle

Dijkstra's algorithm maintains a set of vertices $S$ for which the shortest path from the source has already been finalized. For all other vertices $v \notin S$ , it maintains a dist[v] value, which is an upper bound on the shortest path distance from the source $s$ to $v$ . Initially, dist[s] is 0 and all other are .

2.2 Algorithm Steps

Initialize dist[s] = 0 for the source vertex $s$ and `dist[v] = \infty $for all other vertices$ v \in V$.
Maintain a min-priority queue (e.g., a min-heap) containing all vertices, prioritized by their current dist values.
While the priority queue is not empty: a. Extract the vertex $u$ with the minimum dist value from the priority queue. b. Add to the set of visited vertices (meaning its shortest path has been finalized). c. For each neighbor of : i. If is not in and , update and update 's priority in the queue.

2.3 Example Walkthrough

Consider the following weighted directed graph:

text

       10
    s ----> u
    |       ^
   5|       |1
    v       |
    |       y
   2|       |9
    x ----> v
     <----  |4
      6     z

Note: The diagram provided in the source was slightly ambiguous with edges $x \to v$ and $v \to x$ . Assuming it's $x \to v$ with weight 6 and $v \to x$ with weight 2 based on the example. Let's adjust to match standard examples, assuming no $x \to$ edge with 6, but with 2 and with 4. And let be 5. Let's use the provided textual example more directly:

Initial state: dist = {s:0, u:inf, v:inf, x:inf, y:inf}. Priority queue PQ = {(s,0), (u,inf), (v,inf), (x,inf), (y,inf)}.

Extract s (dist=0).
- Neighbors of s: u (weight 10), v (weight 5).
- dist[u] = min(inf, dist[s] + 10) = 10. Update PQ.
- dist[v] = min(inf, dist[s] + 5) = 5. Update PQ.
- dist = {s:0, u:10, v:5, x:inf, y:inf}. PQ = {(v,5), (u,10), (x,inf), (y,inf)}.
Extract v (dist=5).
- Neighbors of v: u (weight 3), (weight 2).

Final shortest paths from s:

s to s: 0
s to v: 5 (path $s \to v$ )
s to x: 7 (path $s \to v \to x$ )
s to : 8 (path )

2.4 Complexity

The time complexity of Dijkstra's algorithm depends on the implementation of the priority queue:

Using a binary heap: $O(E \log V)$ , where $E$ is the number of edges and $V$ is the number of vertices.
Using a Fibonacci heap: $O(E + V \log V)$ , which is asymptotically faster for dense graphs.

2.5 C++ Implementation Example

Here's a C++ implementation of Dijkstra's algorithm using std::priority_queue:

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits
 
const long long INF = std::numeric_limits<long long>::max();
 
// Pair represents (distance, vertex_id)
typedef std::pair<long long, int> diPair;
 
// Dijkstra's algorithm function
std::vector<long long> dijkstra(int V, const std::vector<std::vector<diPair>>& adj, int start_node) {
    // dist[i] stores the shortest distance from start_node to i

3. All-Pairs Shortest Path (APSP): Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with negative edge weights, but not negative cycles (as a path length would then approach $-\infty$ ).

3.1 Principle

The algorithm iteratively improves an estimate of the shortest path between all pairs of vertices. It considers all possible intermediate vertices $k$ such that a path from $i$ to $j$ might become shorter by passing through $k$ .

Let $D^{(k)}[i][j]$ be the shortest path distance from vertex $i$ to vertex $j$ using only vertices from the set $\{1, 2, \dots, k\}$ as intermediate vertices.

3.2 Algorithm Steps

Initialize a distance matrix $D[i][j]$ :
- $D[i][j] = w(i, j)$ if there is an edge from $i$ to $j$ .

3.3 Example Illustration

Consider a graph with 3 vertices (0, 1, 2) and initial weights: Edges: $(0,1)=3, (0,2)=8, (1,2)=2, (1,0)=5, (2,0)=1$

Initial Distance Matrix $D^{(0)}$ :

text

      0   1   2
   0 [0,  3,  8]
   1 [5,  0,  2]
   2 [1, INF, 0]

After $k=0$ (allowing 0 as an intermediate vertex):

$D[1][2] = \min(D[1][2], D[1][0] + D[0][2]) = \min(2, 5 + 8) = \min(2, 13) = 2$

$D^{(1)}$ :

text

      0   1   2
   0 [0,  3,  8]
   1 [5,  0,  2]
   2 [1, INF, 0]

After $k=1$ (allowing 1 as an intermediate vertex):

$D[0][2] = \min(D[0][2], D[0][1] + D[1][2]) = \min(8, 3 + 2) = \min(8, 5) = 5$

After considering $k=1$ , the matrix will look something like this (assuming $D[2][1]$ remains $\infty$ for simplicity based on initial state):

$D^{(2)}$ :

text

      0   1   2
   0 [0,  3,  5]
   1 [5,  0,  2]
   2 [1, INF, 0]

The algorithm continues for $k=2$ .

3.4 Negative Cycles Detection

If after all iterations $k$ , for any vertex $i$ , $D[i][i] < 0$ , then the graph contains a negative cycle. This is because if a path from $i$ to $i$ becomes negative, it means a cycle exists where traversing it reduces the total path length, making the concept of a "shortest path" ill-defined (you could traverse it infinitely to get $- \infty$ ).

3.5 Complexity

The time complexity of the Floyd-Warshall algorithm is $O(V^3)$ , where $V$ is the number of vertices. This is due to the three nested loops, each iterating up to $V$ times. The space complexity is $O(V^2)$ to store the distance matrix.

4. Comparison and Applications

Applications:

GPS and Map Navigation: Finding the shortest route between two points.
Network Routing: Determining the most efficient paths for data packets in computer networks.
Logistics and Transportation: Optimizing delivery routes and scheduling.
Resource Allocation: Finding optimal paths in dependency graphs.
Flight Planning: Calculating minimum-cost itineraries.

Summary

Shortest Path Algorithms find paths with minimum total weight in weighted graphs.
The two main problems are Single-Source Shortest Path (SSSP) and All-Pairs Shortest Path (APSP).
Dijkstra's Algorithm solves SSSP for graphs with non-negative edge weights using a greedy approach, often implemented with a min-priority queue for $O(E \log V)$ efficiency.
Floyd-Warshall Algorithm solves APSP for graphs with any edge weights (excluding negative cycles) using a dynamic programming approach, with an $O(V^3)$ time complexity.
The choice between algorithms depends on whether a single source or all pairs of shortest paths are needed, and whether negative edge weights are present.

Assessed progress

Shortest Path Algorithms

Shortest Path Algorithms

1. Introduction to Shortest Path Problems

2. Single-Source Shortest Path (SSSP): Dijkstra's Algorithm

2.1 Principle

2.2 Algorithm Steps

2.3 Example Walkthrough

2.4 Complexity

2.5 C++ Implementation Example

3. All-Pairs Shortest Path (APSP): Floyd-Warshall Algorithm

3.1 Principle

3.2 Algorithm Steps

3.3 Example Illustration

3.4 Negative Cycles Detection

3.5 Complexity

4. Comparison and Applications

Summary

Key Concepts

Weighted Graph

Path Length

Single-Source Shortest Path (SSSP)

Dijkstra's Algorithm

All-Pairs Shortest Path (APSP)

Floyd-Warshall Algorithm

Quick Check

Advanced Data Structures

Advanced Data Structures