Variants of Shortest Path Algorithms

Variants of Dijkstra Algorithm

Dijkstra algorithm is a classic method for solving single-source shortest path problems, but its original form has limitations when handling negative-weight edges. Common variants include:

  • Heap-based variants: Use priority queues (e.g., Fibonacci heaps) instead of ordinary queues, significantly reducing time complexity, suitable for large graphs.
  • Topological Sorting variants: Preprocess node order via topological sorting to reduce time complexity to O(V+E), avoiding redundant relaxation operations.
  • Dynamic graph variants: Support dynamic edge weight updates, using dynamic distance tables for real-time path computation.
    Applications: Used in social networks to quickly find shortest connection paths between users, or in traffic navigation for real-time path planning under dynamic conditions.

Variants of Floyd-Warshall Algorithm

Floyd-Warshall algorithm calculates all-pairs shortest paths via dynamic programming. Variants focus on efficiency or specific scenarios:

  • Sparse graph optimization: Introduce boolean arrays to mark unvisited nodes, reducing redundant calculations, lowering time complexity from O(V³) to O(V² + E).
  • Dynamic weight updates: Allow online modification of edge weights, enabling re-computation via re-running the algorithm or incremental updates.
  • Constraint-based shortest paths: Add constraints (e.g., maximum flow, minimum time) to original algorithm, solving complex problems via multi-stage dynamic programming.
    Notes: Variants of Floyd-Warshall are suitable for small-scale graphs but may not be efficient for large-scale networks due to high time complexity.

Variants of A* Algorithm

A* combines Dijkstra's shortest path solving capability with heuristic search efficiency, with variants tailored to different scenarios:

  • Heuristic function adjustments: Select different heuristic functions (e.g., Manhattan distance, Chebyshev distance) based on problem characteristics, balancing exploration efficiency and path accuracy.
  • Hierarchical A* (HSA*): Divides search space into multiple layers to reduce complexity, suitable for high-dimensional spaces or complex terrains.
  • Bidirectional A***: Searches simultaneously from start and end points, significantly reducing search space, ideal for large maps.
    **Typical applications    : Used in autonomous driving for real-time path planning, dynamically adjusting heuristic functions based on real-time traffic data.

Variants of Bellman-Ford Algorithm

Bellman-Ford detects negative-weight cycles via relaxation operations. Variants address specific problems:

  • SPFA (Shortest Path Faster Algorithm): A queue-based variant optimized for Bellman-Ford, dynamically adjusting node enqueue frequencies to reduce time complexity, suitable for graphs with negative-weight edges.
  • Multi-source shortest paths: Initialize all node distances to 0 for multi-source shortest path computation, suitable for scenarios requiring simultaneous consideration of multiple start points.
  • Negative-weight cycle detection: Incorporates cycle detection mechanisms, using node relaxation counts to identify negative-weight cycles, providing basis for subsequent path adjustments.
    Limitations: Variants of Bellman-Ford may lack efficiency for large-scale graphs due to high time complexity, requiring integration with other algorithms for optimization.

Variants of Graph-Based Shortest Path Methods

Beyond the above algorithms, some methods leverage graph theory properties:

  • Kruskal's path optimization: Records parent node information during minimum spanning tree construction to indirectly solve shortest paths, suitable for specific graph structures.
  • Priority queue variants of Dijkstra: Replace traditional heaps with skip lists or B+ trees to improve query and update efficiency.
  • Hierarchical traversal: Divides graphs into multiple layers (e.g., layered graphs), reducing search space via distance relations, suitable for layered structure path planning.
    Summary: Variants of shortest path algorithms expand traditional algorithms' applicability, offering more options for complex scenarios. Each variant prioritizes time complexity, space complexity, and application scenarios, requiring selection based on specific problems.