Advance Analysis of Algorithm Notes

Dijkstra’s Algorithm
1. Definition

Dijkstra’s algorithm is a single-source shortest-path algorithm used to find the

minimum-cost path from a given source node to all other nodes in a weighted graph
with non-negative edge weights. Proposed by Edsger W. Dijkstra in 1956, published
in 1959. Originally designed to solve shortest-path problems in telecommunication
networks. Became the foundation for routing protocols and graph theory applications.
It guarantees the optimal shortest path.

2. Problem Definition

A weighted graph 𝐺 = (𝑉, 𝐸, 𝑤 ) with non-negative edge weights.

Where:

𝑉 = 𝑠𝑒𝑡 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠
𝐸 = 𝑠𝑒𝑡 𝑜𝑓 𝑒𝑑𝑔𝑒𝑠
𝑤 = (𝑢, 𝑣 ) ≥ 0 = 𝑤𝑒𝑖𝑔ℎ𝑡 (𝑐𝑜𝑠𝑡) 𝑜𝑓 𝑒𝑑𝑔𝑒

Find the shortest path from a source node to all other nodes (single-source shortest
path).
3. Working Principle

 Dijkstra’s algorithm is based on greedy selection.

 At each step, it selects the node which has the smallest tentative distance
from the source and permanently fixes its shortest distance.
 Once a node is selected, its distance will never change.

4. Algorithm Steps

I. Assign distance 0 to source node and ∞ to all other nodes.

II. Insert all nodes into a min-priority queue.
III. Repeat:
 Remove the node with the smallest distance.
 For each neighbor of this node:
o If a shorter path is found, update its distance.
 IV. Stop when the destination node is reached.

5. Mathematical Relation (Relaxation)

For an edge (𝑢, 𝑣 ):

𝐼𝑓 𝑑(𝑣 ) > 𝑑 (𝑢) + 𝑤 (𝑢, 𝑣 ) 𝑡ℎ𝑒𝑛 𝑑(𝑣 ) = 𝑑 (𝑢) + 𝑤 (𝑢, 𝑣)

This process is called edge relaxation.

6. Complexity Analysis

Using a binary heap priority queue:

Time Complexity: 𝑂((𝑉 + 𝐸 ) log 𝑉).

Space Complexity: 𝑂 (𝑉 + 𝐸 )

7. Use in the Research Paper

In the uploaded paper, Dijkstra’s algorithm is used as the baseline reference

algorithm.

It provides:

 True shortest-path distances

 Training labels for AI models
 Correctness verification for A*, AI-A*, and Neural models

All other algorithms are compared against Dijkstra.

8. Performance on Different Graphs (from the paper)

I. Grid Graphs

Dijkstra explores many nodes because it has no heuristic.

A* performs better here.

II. Erdős–Rényi (Random Graphs)

A* uses heuristic = 0, so A* ≈ Dijkstra.

Both have almost identical runtime.

III. Scale-Free Graphs

Dijkstra performs reliably but explores many nodes due to high-degree hubs.
9. Time and Space Complexity
Time Complexity:
• with binary heap.
• Efficient for sparse graphs, slower for dense graphs.
Memory Usage:

• Stores distance array + priority queue →𝑂(|𝑉|).

• Memory scales linearly with number of nodes.
Space Trade-Off:
• Adjacency list representation keeps space manageable.
• Larger graphs → more memory overhead in queue operations.
Trade-Off Summary:
• Fast & memory-efficient for non-negative weights.
• Cannot handle negative weights.
• Serves as baseline in experiments.
10. Advantages
 Always gives the correct shortest path
 Simple and stable
 Efficient for sparse graphs.
 Works on any non-negative weighted graph
 Widely implemented in libraries (e.g., NetworkX, Boost).
 Forms the basis of many routing protocols (OSPF, IS-IS).

11. Limitations

 Cannot handle negative edge weights.

 Performance degrades on dense graphs (many edges).
 No heuristic guidance → explores broadly, even when target is far.
 Memory usage grows with graph size
 Slower than A* when a good heuristic exists
 Explores unnecessary nodes.

12. Variants

 Bidirectional Dijkstra: Runs from source and target simultaneously,

meeting in the middle.
 Multi-source Dijkstra: Starts with multiple sources.
  Dynamic Dijkstra: Adapts to changing edge weights (used in traffic
routing).
 Early Termination: Stops once target node is reached (single-pair
optimization).

13. Applications
 Networking: Internet routing protocols (OSPF, IS-IS).
 Maps & GPS: Google Maps, navigation systems.
 Robotics: Path planning for autonomous robots.
 Information Retrieval: Ranking documents by similarity.
 Game Development: NPC pathfinding in grid-based maps.

14. In This Paper

 Used as the baseline algorithm.
 Compared against A*, Bellman-Ford, AI-Augmented A*, and Neural
Baseline.
 Findings:
o Slower than A* when heuristic is good.
o Faster than Bellman-Ford.
o More reliable than ML-based methods.
 Serves as the ground truth for training ML models (labels for GNN
regression).

A* (A-Star) Algorithm

1. Definition

Introduced in 1968 by Hart, Nilsson, and Raphael. Designed for pathfinding and graph
traversal in AI systems. Became the standard in robotics, gaming, and navigation
because it balances optimality and efficiency. A* is a heuristic-based shortest-path
algorithm used to find the minimum-cost path between a source node and a
destination node.

It is an extension of Dijkstra’s algorithm that uses additional information (a

heuristic) to guide the search toward the goal more efficiently.

2. Core Idea

Dijkstra selects nodes only by the distance already travelled.

A* selects nodes based on:

𝑓 (𝑛) = 𝑔(𝑛) + ℎ(𝑛)

Where:

 𝑔(𝑛)= cost from source to node 𝑛

 ℎ(𝑛)= estimated cost from 𝑛 to target
 𝑓 (𝑛)= estimated total path cost

This allows A* to move toward the goal instead of expanding blindly.

3. Algorithm Steps

I. Set 𝑔 (𝑠) = 0 and compute 𝑓 (𝑠) = ℎ(𝑠)

II. Insert the source node into a priority queue ordered by 𝑓 (𝑛)
III. Repeat:
o Remove the node with the smallest 𝑓 (𝑛)
o For each neighbor:
 Compute new 𝑔 and 𝑓
 Update if shorter

IV. Stop when the target is selected

4. Time and Space Complexity

 Time Complexity:

 Worst case (bad heuristic): 𝑂((𝑉 + 𝐸 ) log 𝑉)

 Best case (good heuristic).
 Much faster than Dijkstra because far fewer nodes are expanded.

 Memory Usage:

 Stores 𝑔(𝑛), ℎ(𝑛), 𝑓(𝑛) for each node → 𝑂(|𝑉|).

 Slightly higher than Dijkstra due to heuristic calculations.
 Memory: 𝑂 (𝑉 + 𝐸 )

 Space Trade-Off:
 Priority queue grows with explored nodes.
 Heuristic storage adds overhead but manageable.

 Trade-Off Summary:

 Time efficiency improves with good heuristics.

 Memory slightly higher than Dijkstra.
 Degenerates to Dijkstra if heuristic is poor.
5. Performance on Different Graphs

Grid Graphs

Manhattan heuristic closely matches real distance.

A* expands far fewer nodes and is faster than Dijkstra.

Erdős–Rényi Graphs

No geometric structure → heuristic = 0

A* behaves exactly like Dijkstra.

Scale-Free Graphs

Heuristic is weak → A* ≈ Dijkstra

6. Advantages

 Much faster than Dijkstra when heuristic is good

 Still gives optimal path
 Reduces node expansions
 Ideal for spatial networks (maps, robotics, GPS)

7. Limitations

 Needs a good heuristic

 If heuristic is poor, performance equals Dijkstra
 Heuristic must be admissible to guarantee correctness

8. Heuristic Function

 Manhattan Distance: For grid graphs (sum of absolute differences in x and y).
 Euclidean Distance: Straight-line distance.
 Domain-specific heuristics: e.g., travel time estimates in road networks.
 Learned heuristics: From ML models (Gradient Boosting, GNN).

9. Variants

 Weighted A*: Allows trade-off between speed and optimality.

 Iterative Deepening A* (IDA*): Memory-efficient version.
 Dynamic A* (D*): Adapts to changing environments (used in robotics).
 AI-Augmented A*: Uses ML predictions as heuristics (studied in this paper).

10. Applications

 Navigation systems: GPS, Google Maps.

 Robotics: Path planning for autonomous vehicles.
  Games: NPC pathfinding in large maps.
 Information retrieval: Ranking search results.
 AI planning: Decision-making in complex environments.

Bellman-Ford Algorithm

1. Definition

Developed by Richard Bellman (1958) and Lester Ford (1956). One of the earliest
algorithms for shortest paths in graphs. Still widely taught because of its theoretical
importance and robustness.

Bellman–Ford is a single-source shortest-path algorithm that can handle negative

edge weights. It finds the shortest path from a source node to all other nodes in a
weighted graph, even when some edges have negative cost.

Unlike Dijkstra and A*, Bellman–Ford does not use a priority queue.

2. Problem Formulation

Given a graph

𝐺 = 𝑉, 𝐸, 𝑤

where weights 𝑤(𝑢, 𝑣) may be positive or negative, but there is no negative

cycle, find the shortest path from source 𝑠 to destination 𝑡.

3. Working Principle

Bellman–Ford works by repeatedly relaxing all edges.

It is based on the idea that the shortest path in a graph with 𝑉 vertices can have at
most 𝑽 − 𝟏 edges.

So, the algorithm relaxes every edge 𝑽 − 𝟏 time to propagate shortest distances.

4. Relaxation Formula

For every edge (𝑢, 𝑣):

𝐼𝑓 𝑑 (𝑣 ) > 𝑑(𝑢) + 𝑤 (𝑢, 𝑣 ), 𝑡ℎ𝑒𝑛 𝑑(𝑣 ) = 𝑑 (𝑢) + 𝑤 (𝑢, 𝑣)

This operation is applied repeatedly to all edges.

5. Algorithm Steps

I. Initialize 𝑑(𝑠) = 0, all other distances = ∞

II. Repeat for 𝑽 − 𝟏 iterations:
a. For every edge (𝑢, 𝑣), apply relaxation
III. (Optional) Run one more iteration to detect negative cycles
IV. The final distances give the shortest paths

This is much slower than Dijkstra and A*.

6. Time and Space Complexity

 Time Complexity:

 Time= 𝑂 (|𝑉|. |𝐸|)

 Much slower than Dijkstra/A*.

 Memory Usage:

 Stores distance array → 𝑂 (|𝑉| ).

 Lower memory footprint than A* (no heuristic).

 Space Trade-Off:

 Simple storage, but repeated relaxations increase runtime.

 Trade-Off Summary:

 High time cost, but low memory overhead.

 Essential for negative weights and cycle detection.
 Sacrifices speed for robustness

7. Advantages

 Handles negative edge weights.

 Can detect negative cycles
 Simple to implement.
 Robust in economic modeling, routing metrics, and graphs where costs can
be negative.

8. Disadvantages
  Slower than Dijkstra and A*.
 Extremely slow for large graphs
 Higher memory usage
 Cannot provide meaningful paths if negative cycles exist (distances keep
decreasing).

9. Variants

 Bellman-Ford-Moore: Early version, similar principle.

 Distributed Bellman-Ford: Used in distance-vector routing protocols (e.g., RIP).
 Optimized Bellman-Ford: Early termination if no updates occur in an iteration.

10. Applications

 Networking: Distance-vector routing protocols (RIP).

 Economics: Detecting arbitrage opportunities (negative cycles = profit loops).
 Graph theory research: Benchmark for negative-weight problems.
 Transportation: Modeling costs that can be negative (discounts, subsidies).

AI-Augmented A*
1. Definition

AI-Augmented A* is a hybrid shortest-path algorithm in which the classical A*

search is guided not by a mathematical heuristic, but by a machine learning models
that predict distances. Improve efficiency by reducing node expansions while still
maintaining near-optimal paths.

It keeps the same A* structure:

𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

but replaces ℎ(𝑛) with a learned model ℎ𝐴𝐼 (𝑛).

2. Core Idea

 Use ML models to approximate the cost-to-go (distance from node to target).

 Integrate predictions into A*’s evaluation function:

𝑓(𝑛) = 𝑔(𝑛) + ℎ𝐴𝐼 (𝑛)

 𝑔(𝑛): exact cost from source to node.

  ℎ𝐴𝐼 (𝑛): predicted cost from node to target (from ML model).

If predictions are accurate and admissible, search efficiency improves.

3. Models Used in This Paper

1. Gradient Boosting Regressor (GBR):

 Uses hand-engineered graph features (degree, edge weights, etc.).

 Predicts approximate shortest-path distances.

2. Graph Neural Network (GNN):

 Learns directly from graph structure.

 Message Passing Neural Network (MPNN) with edge-weight-aware
aggregation.
 Outputs scalar distance predictions per node.

4. Step-by-Step Procedure

1. Training Phase

 Generate ground-truth shortest-path distances using Dijkstra.

 Train ML models (GBR, GNN) to predict distances.

2. Integration into A*

 Replace heuristic ℎ(𝑛) with ML prediction ℎ𝐴𝐼 (𝑛):.

 Run A* with this augmented heuristic.

3. Evaluation

 Measure runtime, memory, and node expansions.

 Compare against classical A*, Dijkstra, Bellman-Ford, and Neural
Baseline.

5. Complexity Analysis

 Time Complexity:

 Classical A* time + ML inference overhead.

 Slower than pure A* due to prediction cost.

 Memory Usage:
  Stores model parameters + predictions.
 Higher than classical A*.

 Space Trade-Off:

 Requires GPU/CPU memory for inference.

 Adds complexity compared to lightweight heuristics.

 Trade-Off Summary:
 Potential time savings from fewer expansions.
 Memory and space overhead from ML models.
 Gains depend on heuristic accuracy vs inference cost.

6. Advantages

 Can outperform classical A* on structured graphs.

 Useful in structured environments (grids, road networks).
 Learns structure from data.
 Can work where no geometric heuristic exists.
 Bridges classical algorithms with modern AI.

7. Limitations

 Inference overhead.
 Requires training data and computational resources.
 Predictions may be inaccurate → risk of suboptimal paths.
 Needs calibration to avoid wrong paths
 Not always better than Dijkstra

8. Applications

 Navigation systems: Learned heuristics adapt to traffic patterns.

 Robotics: Path planning in complex environments.
 Large-scale networks: Where handcrafted heuristics are hard to design.
 AI research: Hybrid classical + learned approaches.
 Neural Baseline (Distance Predictor)
1. Definition

The Neural Baseline is a pure machine-learning approach that predicts the shortest-
path distance between a source node 𝑠 and a target node 𝑡 without running any graph-
search algorithm. Specifically, it is a Graph Neural Network (GNN) trained to
approximate shortest-path distances. Instead of following deterministic rules, it learns
patterns in graph structures and predicts distances directly.

It does not use Dijkstra, A*, or Bellman-Ford during inference.

2. Core Idea

 Each node is represented by a feature vector.

 The GNN propagates information across edges using message passing.
 Edge weights influence the messages exchanged between nodes.
 After several layers, the network outputs a predicted distance for each node.

3. Model Used

Two types of learning models are evaluated:

a. Gradient Boosting Regressor

Uses:

 Degree of source node

 Degree of target node
 Clustering coefficient
 Local graph features

b. Graph Neural Network (GNN)

Uses:

 Node connections
 Edge weights
 Message passing between nodes

Both models are trained using:

𝑇𝑎𝑟𝑔𝑒𝑡 = 𝑇𝑟𝑢𝑒 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑓𝑟𝑜𝑚 𝐷𝑖𝑗𝑘𝑠𝑡𝑟𝑎

4. Working Mechanism

Given (𝑠, 𝑡):

1. Extract node features

2. Feed them to the ML model
3. Model outputs:

𝑑̂ (𝑠, 𝑡) = 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒

No search, no expansion, no priority queue

5. Complexity Analysis

 Time Complexity:

 Slowest method: 2.60x–3.23x slower than A*.

 Heavy matrix multiplications and message passing.

 Memory Usage:

 High due to storing model weights + activations.

 GPU VRAM usage significant (≥16 GB in experiments)

 Space Trade-off:

 Requires large memory footprint for training/inference.

 Not scalable for very large graphs.

 Trade-Off Summary:

 Poor time efficiency compared to classical algorithms.

 High memory/space cost.
 Limited as solver, better as heuristic generator.

6. Why Neural Baseline Fails as a Solver

Shortest path depends on:

 Entire graph topology

 Global constraints

But the neural model sees:

 Only local node features

Therefore, it cannot guarantee correctness.

 7. Advantages

 Extremely fast inference

 Learns heuristics automatically from data.
 Potential to generalize across different graph types.
 Useful as a heuristic generator for A*.

8. Disadvantages

 Memory-heavy due to neural computations.

 Predictions approximate, not guaranteed exact.
 Poor generalization to unseen graph sizes/topologies.
 Requires large training datasets and GPU resources.

9. Applications

 Research baseline: Compare AI vs classical algorithms.

 Heuristic generation: Provide learned heuristics for A*.
 Complex domains: Where handcrafted heuristics are difficult.
 Experimental AI systems: Testing hybrid classical + learned approaches.

Comparative Trade-Off Table

Method Time Efficiency Memory Usage Space Trade-Off Best Use Case

Non-negative
Priority queue +
Dijkstra Moderate (baseline) Low–Moderate weights, general-
adjacency list
purpose baseline

Grid / road networks

Fast (with good Extra storage for
A* Moderate with strong
heuristic) heuristic values
heuristics
Negative weights,
Simple distance
Bellman–Ford Slow (O(V·E)) Low negative-cycle
array
detection
Priority queue + Domains with
Variable (depends
AI-Augmented A* High ML model + learned or data-
on ML quality)
feature storage driven heuristics

Slowest (as a Heavy ML / GPU Research baseline,

Neural Baseline Highest
solver) footprint heuristic generator