Paper Summaries
1. Abousleiman - "A Bellman-Ford Approach to Energy Efficient Routing of Electric Vehicles"
Focus: Energy-efficient routing for electric vehicles (EVs)
- Traditional Dijkstra algorithms optimize for shortest distance or time but NOT energy
- Electric vehicles present unique challenges: negative path costs (from regenerative braking)
- Battery power and energy limits make EV routing fundamentally different from fossil fuel vehicles
- Solution: Uses Bellman-Ford algorithm instead, which can handle negative edge weights
- Bellman-Ford is deterministic and effective for EV routing optimization
Key Insight: Dijkstra CANNOT be used for EV routing due to negative costs from regenerative braking; Bellman-Ford is the appropriate alternative.
2. Abusalim - "Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization"
Focus: Direct comparison of two major shortest path algorithms
- Dijkstra's Algorithm: Better execution time, more efficient for shortest path problems
- Bellman-Ford Algorithm: Can handle negative edge weights, less efficient overall
- Primary Limitation of Dijkstra: Works ONLY with non-negative edge weights
- Applications: Computer protocols, GPS/Google Maps, game development
Key Insight: Choose algorithm based on edge weight constraints—Dijkstra for non-negative, Bellman-Ford for graphs with negative weights.
3. Bing - "Improvement and Application of Dijkstra Algorithms"
Focus: Optimization of Dijkstra algorithm for practical efficiency
- Classic Dijkstra is exhaustive and calculates many routes NOT in final solution
- Algorithm complexity: O(n²) where n = number of nodes
- Proposed improvements: Improved calculation method, graphical model modification
- Applications: Traffic route planning, logistics, network optimization, robot navigation
Key Insight: Classic Dijkstra has O(n²) complexity and is inefficient; improved versions reduce calculation overhead by being more directional.
4. Duan et al. - "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths"
Focus: BREAKTHROUGH - First algorithm to beat Dijkstra's proven bounds
- Developed O(m log^(2/3) n) algorithm - FIRST to break O(m + n log n) Dijkstra bound!
- Proves Dijkstra's algorithm is NOT optimal for sparse directed graphs
- Works on directed graphs with real non-negative edge weights
- Breaks the sorting bottleneck that limited previous improvements
Key Insight: For almost 70 years, Dijkstra was considered optimal; this research proves it can be improved for sparse directed graphs.
5. Duan et al. - "A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs"
Focus: Breaking Dijkstra's bound for undirected graphs
- NEW randomized algorithm with O(m √log n log log n) time
- First to break O(m + n log n) Dijkstra bound for real-weighted sparse graphs
- Non-hierarchy-based approach (simpler structure, easier implementation)
- Comparable to Thorup's linear time for integer edge weights
Key Insight: Randomization enables beating Dijkstra; algorithm is practical and easier to implement than previous approaches.
6. Fan & Shi - "Improvement of Dijkstra's Algorithm and Its Application in Route Planning"
Focus: Practical improvements for road network route planning
- Storage Structure Improvement: Replace adjacency matrix with more efficient structures
- Searching Area Restriction: Limit search space to relevant regions
- Applications: Road network path planning, vehicle navigation, logistics
Key Insight: Classic Dijkstra needs improvements in data structure and search space restriction for practical efficiency.
7. Haeupler et al. - "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps"
Focus: Proving Dijkstra is universally optimal with proper heap implementation
- With sufficiently efficient heap, Dijkstra's algorithm is universally optimal
- Universal optimality = performs as well as possible on EVERY graph
- New Heap Data Structure with Working-Set Bound for efficiency
- Proves Dijkstra optimal for ordering vertices by distance
Key Insight: Dijkstra IS provably optimal with the right heap implementation.
8. Javaid - "Understanding Dijkstra's Algorithm"
Focus: Clear educational explanation of Dijkstra's algorithm
- Solves single-source shortest paths problem
- Finds least-cost routes from starting node to all other nodes
- Uses table-based systematic approach with visited column and next row
- Applications: Network routing, GPS navigation, cost minimization
Key Insight: Dijkstra provides systematic table-based method for finding shortest paths.
9. Mo et al. - "Robustness of the Adaptive Bellman-Ford Algorithm: Global Stability and Ultimate Bounds"
Focus: Distributed systems application; robustness of Bellman-Ford
- Important for distributed systems (Aggregate Programming)
- Classical Bellman-Ford lacks robustness properties under perturbations
- Formulates Lyapunov function to analyze Adaptive Bellman-Ford
- Proves GLOBAL UNIFORM ASYMPTOTIC STABILITY
- Applications: Distributed services, IoT systems, Aggregate Computing
Key Insight: Bellman-Ford can be made robust for distributed systems through adaptive mechanisms.
10. Rachmawati & Gustin - "Analysis of Dijkstra's Algorithm and A* Algorithm in Shortest Path Problem"
Focus: Comparing Dijkstra with A* (heuristic improvement)
- Small/Regional Scale Maps: Dijkstra and A* perform similarly
- Large Scale Maps: A* significantly outperforms Dijkstra
- A* uses heuristic to guide search (unlike Dijkstra's exhaustive approach)
- Applications: GPS navigation, finding nearest locations, route planning
Key Insight: For small to medium problems, Dijkstra and A* are comparable; A* scales better for large maps.