10.1 Single-source shortest path problem

The single-source shortest path problem is a key concept in graph theory, finding the shortest paths from one vertex to all others. It's crucial for optimizing routes in networks, transportation, and GPS navigation, making it a fundamental tool for efficiency in various real-world scenarios.

This problem builds on the basic shortest path concept, extending it to multiple destinations. It requires a weighted graph, a source vertex, and considers edge weights. The solution must satisfy the optimal substructure property, with special considerations for negative edge weights.

Single-source Shortest Path Problem

Definition and Significance

• Single-source shortest path problem finds shortest paths from a designated source vertex to all other vertices in a weighted graph
• Fundamental in graph theory with applications in network routing, transportation systems, and GPS navigation
• Optimizes resource allocation, minimizes costs, and improves efficiency in various real-world scenarios (logistics, supply chain management)
• Serves as building block for complex graph algorithms in social network analysis and artificial intelligence
• Generalizes the shortest path problem between two specific vertices
• Crucial for developing efficient algorithms in operations research and computer networking

Problem Components

• Requires weighted graph G = (V, E), where V represents vertices and E represents edges
• Designated source vertex s ∈ V specified as starting point for all shortest paths
• Edge weights w(u, v) represent cost or distance between vertices u and v (can be positive, negative, or zero)
• Solution provides shortest path and total weight from source vertex s to every other vertex v ∈ V
• Valid solution satisfies optimal substructure property (subpaths of shortest paths are themselves shortest paths)
• Assumes graph is connected or all vertices are reachable from source vertex
• Special considerations for graphs with negative edge weights (can lead to negative cycles and potentially unsolvable instances)

Components of the Shortest Path Problem

Graph Representation

• Adjacency matrix representation stores graph as 2D array, suitable for dense graphs
  • Space complexity: $O(V^2)$
  • Time complexity for edge lookup: $O(1)$
• Adjacency list representation stores graph as list of linked lists, efficient for sparse graphs
  • Space complexity: $O(V + E)$
  • Time complexity for edge lookup: $O(degree(v))$
• Edge list representation stores graph as list of edges, useful for certain algorithms (Bellman-Ford)
  • Space complexity: $O(E)$
  • Time complexity for edge lookup: $O(E)$

Path Representation

• Path typically represented as sequence of vertices or edges
• Often stored using predecessor array to reconstruct path
• Total path weight calculated by summing individual edge weights
• Path representation crucial for algorithm implementation and solution retrieval
• Example path representation: [A, B, D, F] for path from vertex A to F

Algorithm Components

• Distance array stores current shortest distance estimates from source to each vertex
• Predecessor array tracks the previous vertex in the current shortest path to each vertex
• Priority queue often used in efficient implementations (Dijkstra's algorithm)
• Relaxation process updates distance estimates and predecessors as shorter paths are found
• Initialization step sets initial distance and predecessor values
• Main loop iteratively processes vertices and updates shortest path estimates

Computational Complexity of Shortest Path Algorithms

Time Complexity Analysis

• Dijkstra's algorithm (non-negative edge weights):
  • Array implementation: $O(V^2)$
  • Binary heap implementation: $O((V + E) \log V)$
  • Fibonacci heap implementation: $O(E + V \log V)$
• Bellman-Ford algorithm (handles negative edge weights):
  • Worst-case time complexity: $O(VE)$
• Breadth-First Search (BFS) for unweighted graphs:
  • Time complexity: $O(V + E)$
• A* search algorithm:
  • Worst-case complexity same as Dijkstra's
  • Better average-case performance with good heuristics
• Floyd-Warshall algorithm (all-pairs shortest path):
  • Time complexity: $O(V^3)$

Space Complexity Considerations

• Most algorithms require $O(V)$ space for storing distances and predecessors
• Dijkstra's algorithm with binary heap: $O(V)$ additional space for the heap
• Floyd-Warshall algorithm: $O(V^2)$ space for distance matrix
• A* search may require additional space for heuristic calculations and open/closed sets
• Space-time tradeoffs possible in some implementations (storing precomputed results)

Weighted vs Unweighted Graphs for Shortest Path Problems

Characteristics and Representations

• Weighted graphs assign numerical value (weight) to each edge (cost, distance, time)
• Unweighted graphs implicitly assign weight of 1 to all edges (count number of edges in path)
• Weighted graph example: Road network with distances between cities
• Unweighted graph example: Social network where edges represent connections between people

Algorithm Applicability

• Weighted graphs require more complex algorithms (Dijkstra's, Bellman-Ford)
• Unweighted graphs can use simpler algorithms like BFS
• BFS efficiently solves single-source shortest path for unweighted graphs in $O(V + E)$ time
• Dijkstra's algorithm simplifies to BFS for unweighted graphs
• Negative edge weights only meaningful in weighted graphs (require Bellman-Ford algorithm)

Modeling Considerations

• Choice between weighted and unweighted representations depends on problem requirements
• Weighted graphs provide more detailed modeling of real-world scenarios
• Unweighted graphs suitable for problems where all connections have equal importance
• Some problems may benefit from converting weighted to unweighted graphs (e.g., rounding weights)
• Hybrid approaches possible (use weights for heuristics in otherwise unweighted graphs)