Report Content

Shortest Path Algorithms: Complete Guide

Master shortest path finding in graphs with Dijkstra's, Bellman-Ford, Floyd-Warshall, and A* algorithms. Learn when to use each method with complexity analysis and real-world applications.

Algorithm Usage in Industry (2023)

Navigation (40%)

Network Routing (25%)

Game AI (20%)

Logistics (15%)

1. Dijkstra's Algorithm

Dijkstra's Shortest Path

Definition

Dijkstra's Algorithm finds the shortest paths from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a greedy approach with a priority queue to always explore the closest unvisited vertex.

How It Works

Initialize distances

Set distance to source = 0, all others = ∞
Add all vertices to priority queue with their distances

Extract minimum vertex

Remove vertex with smallest distance from queue
If distance is outdated, skip

Relax edges

For each neighbor, calculate new distance = current + edge weight
If new distance < known distance, update and re-add to queue

Repeat

Continue until queue is empty
All shortest paths are found

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    predecessors = {node: None for node in graph}
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph[u]:
            distance = current_dist + weight
            if distance < distances[v]:
                distances[v] = distance
                predecessors[v] = u
                heapq.heappush(pq, (distance, v))
    
    return distances, predecessors

# Get shortest path from start to target
def get_path(predecessors, target):
    path = []
    while target is not None:
        path.append(target)
        target = predecessors[target]
    return path[::-1]

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    enqueue(node, priority) {
        this.heap.push({node, priority});
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue() {
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }
    
    bubbleUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.heap[parent].priority <= this.heap[index].priority) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }
    
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;
        
        if (left < this.heap.length && this.heap[left].priority < this.heap[smallest].priority)
            smallest = left;
        if (right < this.heap.length && this.heap[right].priority < this.heap[smallest].priority)
            smallest = right;
        
        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this.sinkDown(smallest);
        }
    }
    
    isEmpty() { return this.heap.length === 0; }
}

function dijkstra(graph, start) {
    const distances = {};
    const predecessors = {};
    const pq = new PriorityQueue();
    
    for (const node in graph) {
        distances[node] = node === start ? 0 : Infinity;
        predecessors[node] = null;
        pq.enqueue(node, distances[node]);
    }
    
    while (!pq.isEmpty()) {
        const {node: u, priority: currentDist} = pq.dequeue();
        
        if (currentDist > distances[u]) continue;
        
        for (const {node: v, weight} of graph[u]) {
            const distance = currentDist + weight;
            if (distance < distances[v]) {
                distances[v] = distance;
                predecessors[v] = u;
                pq.enqueue(v, distance);
            }
        }
    }
    
    return {distances, predecessors};
}

import java.util.*;

public class Dijkstra {
    static class Edge {
        int target, weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    
    static class Node implements Comparable<Node> {
        int id, distance;
        Node(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
    
    public static int[] dijkstra(List<List<Edge>> graph, int start, int n) {
        int[] dist = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.id;
            int currentDist = current.distance;
            
            if (currentDist > dist[u]) continue;
            
            for (Edge edge : graph.get(u)) {
                int v = edge.target;
                int newDist = currentDist + edge.weight;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.offer(new Node(v, newDist));
                }
            }
        }
        return dist;
    }
}

#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii;

vector<int> dijkstra(vector<vector<pii>>& graph, int start, int n) {
    vector<int> dist(n, INT_MAX);
    vector<int> prev(n, -1);
    dist[start] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();
        
        if (currentDist > dist[u]) continue;
        
        for (auto [v, weight] : graph[u]) {
            int newDist = currentDist + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                prev[v] = u;
                pq.push({newDist, v});
            }
        }
    }
    return dist;
}

Complexity: O((V+E) log V) with binary heap, O(V²) with array
Constraints: No negative edge weights
Use When: Single-source shortest paths in non-negative graphs

2. Bellman-Ford Algorithm

Bellman-Ford Shortest Path

Definition

Bellman-Ford Algorithm computes shortest paths from a source vertex to all other vertices in a weighted graph, even when negative edge weights exist. It can also detect negative weight cycles.

How It Works

Initialize distances

Set distance to source = 0, all others = ∞
Store edges in list for easy iteration

Relax edges repeatedly

Repeat V-1 times: iterate through all edges
If dist[u] + weight < dist[v], update dist[v]

Check for negative cycles

Run one more relaxation pass
If any distance improves, negative cycle exists

def bellman_ford(vertices, edges, start):
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0
    predecessors = {v: None for v in vertices}
    
    # Relax edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                predecessors[v] = u
    
    # Check for negative cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("Graph contains negative weight cycle")
    
    return distances, predecessors

# Example usage
vertices = ['A', 'B', 'C', 'D']
edges = [
    ('A', 'B', 4), ('A', 'C', 2),
    ('B', 'C', 1), ('B', 'D', 5),
    ('C', 'D', 8)
]
dist, pred = bellman_ford(vertices, edges, 'A')

function bellmanFord(vertices, edges, start) {
    const distances = {};
    const predecessors = {};
    
    // Initialize
    for (const v of vertices) {
        distances[v] = v === start ? 0 : Infinity;
        predecessors[v] = null;
    }
    
    // Relax edges V-1 times
    for (let i = 0; i < vertices.length - 1; i++) {
        for (const {u, v, weight} of edges) {
            if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
                predecessors[v] = u;
            }
        }
    }
    
    // Check for negative cycles
    for (const {u, v, weight} of edges) {
        if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
            throw new Error("Graph contains negative weight cycle");
        }
    }
    
    return {distances, predecessors};
}

import java.util.*;

public class BellmanFord {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    
    public static int[] bellmanFord(int n, List<Edge> edges, int start) {
        int[] dist = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[start] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != Integer.MAX_VALUE && 
                    dist[e.u] + e.weight < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.weight;
                    prev[e.v] = e.u;
                }
            }
        }
        
        // Check for negative cycles
        for (Edge e : edges) {
            if (dist[e.u] != Integer.MAX_VALUE && 
                dist[e.u] + e.weight < dist[e.v]) {
                throw new RuntimeException("Negative cycle detected");
            }
        }
        
        return dist;
    }
}

#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int u, v, weight;
};

vector<int> bellmanFord(int n, vector<Edge>& edges, int start) {
    vector<int> dist(n, INT_MAX);
    vector<int> prev(n, -1);
    dist[start] = 0;
    
    // Relax edges V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (const Edge& e : edges) {
            if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.weight;
                prev[e.v] = e.u;
            }
        }
    }
    
    // Check for negative cycles
    for (const Edge& e : edges) {
        if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
            throw runtime_error("Negative cycle detected");
        }
    }
    
    return dist;
}

Complexity: O(V×E) time, O(V) space
Advantage: Handles negative edges, detects negative cycles
Use When: Graphs with negative edge weights

3. Floyd-Warshall Algorithm

Floyd-Warshall (All-Pairs Shortest Path)

Definition

Floyd-Warshall Algorithm finds shortest paths between all pairs of vertices in a weighted graph. It uses dynamic programming to consider each vertex as a potential intermediate point.

How It Works

Initialize distance matrix

dist[i][j] = 0 if i == j
dist[i][j] = weight(i,j) if edge exists
dist[i][j] = ∞ if no direct edge

Consider each vertex as intermediate

For k from 0 to V-1:
For i from 0 to V-1, j from 0 to V-1:

Update using dynamic programming

If dist[i][k] + dist[k][j] < dist[i][j]:
Update dist[i][j] = dist[i][k] + dist[k][j]

def floyd_warshall(graph, n):
    # Initialize distance matrix
    dist = [[float('inf')] * n for _ in range(n)]
    next_node = [[None] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
        next_node[i][i] = i
    
    for u, v, w in graph:
        dist[u][v] = w
        next_node[u][v] = v
    
    # Dynamic programming
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]
    
    # Check for negative cycles
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError("Graph contains negative cycle")
    
    return dist, next_node

# Reconstruct path
def get_path(next_node, i, j):
    if next_node[i][j] is None:
        return []
    path = [i]
    while i != j:
        i = next_node[i][j]
        path.append(i)
    return path

function floydWarshall(graph, n) {
    // Initialize distance matrix
    const dist = Array(n).fill().map(() => Array(n).fill(Infinity));
    const next = Array(n).fill().map(() => Array(n).fill(null));
    
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
        next[i][i] = i;
    }
    
    for (const {u, v, w} of graph) {
        dist[u][v] = w;
        next[u][v] = v;
    }
    
    // Dynamic programming
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
    
    // Check for negative cycles
    for (let i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            throw new Error("Negative cycle detected");
        }
    }
    
    return {dist, next};
}

public class FloydWarshall {
    public static int[][] floydWarshall(int[][] graph, int n) {
        int[][] dist = new int[n][n];
        
        // Initialize distance matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // Dynamic programming
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && 
                        dist[k][j] != Integer.MAX_VALUE &&
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        // Check for negative cycles
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                throw new RuntimeException("Negative cycle detected");
            }
        }
        
        return dist;
    }
}

#include <vector>
#include <climits>
using namespace std;

vector<vector<int>> floydWarshall(vector<vector<int>>& graph, int n) {
    vector<vector<int>> dist = graph;
    
    // Dynamic programming
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && 
                    dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // Check for negative cycles
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            throw runtime_error("Negative cycle detected");
        }
    }
    
    return dist;
}

Complexity: O(V³) time, O(V²) space
Advantage: Simpler implementation, finds all-pairs
Use When: Dense graphs or when all-pairs needed

4. A* Search Algorithm

A* (A-Star) Pathfinding

Definition

A* Search is an informed graph traversal algorithm that finds the shortest path using a heuristic to guide its search. It combines Dijkstra's algorithm (uniform cost) with Greedy Best-First Search (heuristic).

How It Works

Initialize scores

gScore: actual cost from start to node
fScore = gScore + heuristic(node, goal)
Priority queue ordered by fScore

Extract best candidate

Pop node with smallest fScore
If node == goal, reconstruct path

Explore neighbors

Calculate tentative gScore
If better than known, update scores
Push neighbors to priority queue

Heuristic must be admissible

Never overestimates true cost
Ensures optimal path (consistent heuristic)

import heapq

def a_star(start, goal, get_neighbors, heuristic):
    open_set = [(0, start)]
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    
    while open_set:
        current_f, current = heapq.heappop(open_set)
        
        if current == goal:
            return reconstruct_path(came_from, current)
        
        for neighbor in get_neighbors(current):
            tentative_g = g_score[current] + get_edge_weight(current, neighbor)
            
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None  # No path found

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return path[::-1]

# Example: Manhattan heuristic for grid
def manhattan_heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

class AStarNode {
    constructor(id, g, f) {
        this.id = id;
        this.g = g;
        this.f = f;
    }
}

function aStar(start, goal, getNeighbors, heuristic, getWeight) {
    const openSet = new PriorityQueue();
    const cameFrom = new Map();
    const gScore = new Map();
    const fScore = new Map();
    
    gScore.set(start, 0);
    fScore.set(start, heuristic(start, goal));
    openSet.enqueue(start, fScore.get(start));
    
    while (!openSet.isEmpty()) {
        const current = openSet.dequeue().element;
        
        if (current === goal) {
            return reconstructPath(cameFrom, current);
        }
        
        for (const neighbor of getNeighbors(current)) {
            const tentativeG = gScore.get(current) + getWeight(current, neighbor);
            
            if (tentativeG < (gScore.get(neighbor) || Infinity)) {
                cameFrom.set(neighbor, current);
                gScore.set(neighbor, tentativeG);
                fScore.set(neighbor, tentativeG + heuristic(neighbor, goal));
                openSet.enqueue(neighbor, fScore.get(neighbor));
            }
        }
    }
    
    return null;
}

function reconstructPath(cameFrom, current) {
    const path = [current];
    while (cameFrom.has(current)) {
        current = cameFrom.get(current);
        path.unshift(current);
    }
    return path;
}

// Manhattan distance for grid pathfinding
function manhattanDistance(pointA, pointB) {
    return Math.abs(pointA.x - pointB.x) + Math.abs(pointA.y - pointB.y);
}

import java.util.*;

public class AStar {
    static class Node implements Comparable<Node> {
        int id;
        double fScore;
        
        Node(int id, double fScore) {
            this.id = id;
            this.fScore = fScore;
        }
        
        public int compareTo(Node other) {
            return Double.compare(this.fScore, other.fScore);
        }
    }
    
    public static List<Integer> aStar(int start, int goal, 
                                       Map<Integer, List<Integer>> getNeighbors,
                                       Map<Integer, Map<Integer, Integer>> getWeight,
                                       Map<Integer, Integer> heuristic) {
        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Map<Integer, Integer> cameFrom = new HashMap<>();
        Map<Integer, Integer> gScore = new HashMap<>();
        Map<Integer, Integer> fScore = new HashMap<>();
        
        gScore.put(start, 0);
        fScore.put(start, heuristic.get(start));
        openSet.offer(new Node(start, fScore.get(start)));
        
        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            int currId = current.id;
            
            if (currId == goal) {
                return reconstructPath(cameFrom, currId);
            }
            
            for (int neighbor : getNeighbors.get(currId)) {
                int tentativeG = gScore.get(currId) + getWeight.get(currId).get(neighbor);
                
                if (tentativeG < gScore.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    cameFrom.put(neighbor, currId);
                    gScore.put(neighbor, tentativeG);
                    fScore.put(neighbor, tentativeG + heuristic.get(neighbor));
                    openSet.offer(new Node(neighbor, fScore.get(neighbor)));
                }
            }
        }
        
        return null;
    }
}

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct AStarNode {
    int id;
    double fScore;
    bool operator>(const AStarNode& other) const {
        return fScore > other.fScore;
    }
};

vector<int> aStar(int start, int goal,
                  unordered_map<int, vector<int>>& neighbors,
                  unordered_map<int, unordered_map<int, int>>& weight,
                  unordered_map<int, int>& heuristic) {
    
    priority_queue<AStarNode, vector<AStarNode>, greater<AStarNode>> openSet;
    unordered_map<int, int> cameFrom;
    unordered_map<int, int> gScore;
    unordered_map<int, int> fScore;
    
    gScore[start] = 0;
    fScore[start] = heuristic[start];
    openSet.push({start, fScore[start]});
    
    while (!openSet.empty()) {
        AStarNode current = openSet.top();
        openSet.pop();
        int currId = current.id;
        
        if (currId == goal) {
            // Reconstruct path
            vector<int> path;
            while (cameFrom.find(currId) != cameFrom.end()) {
                path.push_back(currId);
                currId = cameFrom[currId];
            }
            path.push_back(start);
            reverse(path.begin(), path.end());
            return path;
        }
        
        for (int neighbor : neighbors[currId]) {
            int tentativeG = gScore[currId] + weight[currId][neighbor];
            
            if (gScore.find(neighbor) == gScore.end() || tentativeG < gScore[neighbor]) {
                cameFrom[neighbor] = currId;
                gScore[neighbor] = tentativeG;
                fScore[neighbor] = tentativeG + heuristic[neighbor];
                openSet.push({neighbor, fScore[neighbor]});
            }
        }
    }
    
    return {};
}

Complexity: O(E) with good heuristic, worst-case O(b^d)
Heuristic: Must be admissible (never overestimate)
Use When: Pathfinding with domain knowledge (navigation, games)

5. Algorithm Comparison & Selection

Algorithm Properties Comparison

Algorithm	Graph Type	Negative Edges	Negative Cycles	Optimal For
Dijkstra's	Weighted	No	No	Single-source
Bellman-Ford	Weighted	Yes	Detects	Single-source
Floyd-Warshall	Weighted	Yes	Detects	All-pairs
A*	Weighted	No	No	Single-pair

6. Real-World Applications

GPS Navigation Systems

Dijkstra/A*: Find fastest route between locations

def gps_navigation(graph, start, destination):
    # Use A* with Euclidean distance heuristic
    def heuristic(a, b):
        return haversine_distance(a, b)
    
    return a_star(start, destination, graph, heuristic)

function gpsNavigation(graph, start, destination) {
    // Use A* with Euclidean distance heuristic
    const heuristic = (a, b) => euclideanDistance(a, b);
    return aStar(start, destination, graph, heuristic);
}

public List<Integer> gpsNavigation(Graph graph, int start, int dest) {
    return aStar(start, dest, graph, this::euclideanDistance);
}

vector<int> gpsNavigation(Graph& graph, int start, int dest) {
    return aStar(start, dest, graph, euclideanDistance);
}

Network Routing (OSPF)

Dijkstra's: Open Shortest Path First protocol

def ospf_routing_table(network_topology, router_id):
    distances, _ = dijkstra(network_topology, router_id)
    return distances

function ospfRoutingTable(networkTopology, routerId) {
    return dijkstra(networkTopology, routerId).distances;
}

public int[] ospfRoutingTable(Graph graph, int routerId) {
    return Dijkstra.dijkstra(graph, routerId, graph.size());
}

vector ospfRoutingTable(Graph& graph, int routerId) {
    return dijkstra(graph, routerId, graph.size());
}

Financial Arbitrage

Bellman-Ford: Detect negative cycles in currency exchange

def detect_arbitrage(exchange_rates):
    # Convert to log negative weights
    graph = convert_to_graph(exchange_rates)
    try:
        distances, _ = bellman_ford(graph, 0)
        return True  # No arbitrage
    except ValueError:
        return False  # Arbitrage opportunity found

function detectArbitrage(exchangeRates) {
    const graph = convertToGraph(exchangeRates);
    try {
        bellmanFord(graph, 0);
        return false; // No arbitrage
    } catch {
        return true; // Arbitrage opportunity found
    }
}

public boolean detectArbitrage(double[][] rates) {
    try {
        bellmanFord(convertToGraph(rates), 0);
        return false;
    } catch (RuntimeException e) {
        return true;
    }
}

bool detectArbitrage(vector<vector<double>>& rates) {
    try {
        bellmanFord(convertToGraph(rates), 0);
        return false;
    } catch (runtime_error&) {
        return true;
    }
}

Game AI Pathfinding

A*: NPC movement with obstacle avoidance

def game_ai_path(start, goal, obstacles):
    def heuristic(a, b):
        return abs(a[0]-b[0]) + abs(a[1]-b[1])
    
    return a_star(start, goal, get_neighbors(obstacles), heuristic)

function gameAIPath(start, goal, obstacles) {
    const heuristic = (a, b) => Math.abs(a.x-b.x) + Math.abs(a.y-b.y);
    return aStar(start, goal, getNeighbors(obstacles), heuristic);
}

public List<Point> gameAIPath(Point start, Point goal, Set<Point> obstacles) {
    return aStar(start, goal, getNeighbors(obstacles), this::manhattanHeuristic);
}

vector<Point> gameAIPath(Point start, Point goal, set<Point>& obstacles) {
    return aStar(start, goal, getNeighbors(obstacles), manhattanHeuristic);
}

Algorithm Selection Guide

Scenario	Recommended Algorithm	Reason
Road networks (non-negative weights)	Dijkstra's with Priority Queue	Most efficient for single-source
Financial arbitrage detection	Bellman-Ford	Detects negative cycles
Small dense graphs (all pairs)	Floyd-Warshall	Precomputes all paths
Game pathfinding with obstacles	A* with Manhattan heuristic	Intelligently explores towards goal
Robotics with unknown environment	Dijkstra's (no heuristic)	Guaranteed optimal path

Shortest Path Implementation Checklist

Choose algorithm based on graph type and requirements

Handle negative weights with Bellman-Ford if needed

Optimize priority queue operations for Dijkstra's

Precompute all-pairs paths if query-heavy (Floyd-Warshall)

Use admissible heuristics for A* optimality

Check for negative cycles in arbitrage problems

Store predecessors for path reconstruction

Pro Tip: For large-scale road networks, combine Dijkstra's with Contraction Hierarchies or ALT heuristics to achieve sub-second query times on continent-scale graphs. For real-time applications, consider bidirectional search which can reduce search space by up to 50%.

You need to be logged in to participate in this discussion.