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. Algorithm Fundamentals

Key Properties:

Algorithm	Graph Type	Handles Negative Weights?	Optimal For
Dijkstra's	Weighted (Non-negative)	❌ No	Single-source
Bellman-Ford	Weighted	✅ Yes	Single-source
Floyd-Warshall	Weighted	✅ Yes	All-pairs
A*	Weighted (Non-negative)	❌ No	Single-pair (Heuristic)

Time Complexities:

Algorithm	Time	Space
Dijkstra (Binary Heap)	O((V+E) log V)	O(V)
Bellman-Ford	O(VE)	O(V)
Floyd-Warshall	O(V³)	O(V²)
A*	O(E)	O(V)

2. Algorithm Implementations

Dijkstra's Algorithm


function dijkstra(graph, start) {
  const distances = {};
  const heap = new PriorityQueue();
  
  // Initialize distances
  for (const vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    heap.enqueue(vertex, distances[vertex]);
  }

  while (!heap.isEmpty()) {
    const { element: u, priority: dist } = heap.dequeue();
    
    for (const { node: v, weight } of graph[u]) {
      const alt = dist + weight;
      if (alt < distances[v]) {
        distances[v] = alt;
        heap.enqueue(v, alt); // Decrease-key operation
      }
    }
  }
  return distances;
}

Optimization: Use Fibonacci heap for O(1) decrease-key

Bellman-Ford Algorithm


function bellmanFord(graph, start) {
  const distances = {};
  const predecessors = {};
  
  // Initialize
  for (const vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    predecessors[vertex] = null;
  }

  // Relax edges repeatedly
  for (let i = 1; i < Object.keys(graph).length; i++) {
    for (const u in graph) {
      for (const { node: v, weight } of graph[u]) {
        if (distances[u] + weight < distances[v]) {
          distances[v] = distances[u] + weight;
          predecessors[v] = u;
        }
      }
    }
  }

  // Check for negative cycles
  for (const u in graph) {
    for (const { node: v, weight } of graph[u]) {
      if (distances[u] + weight < distances[v]) {
        throw "Graph contains negative weight cycle";
      }
    }
  }

  return { distances, predecessors };
}

3. Advanced Techniques

Floyd-Warshall (All-Pairs)


function floydWarshall(graph) {
  const dist = {};
  const vertices = Object.keys(graph);
  
  // Initialize distance matrix
  for (const u of vertices) {
    dist[u] = {};
    for (const v of vertices) {
      dist[u][v] = u === v ? 0 : Infinity;
    }
    for (const { node: v, weight } of graph[u]) {
      dist[u][v] = weight;
    }
  }

  // Dynamic programming step
  for (const k of vertices) {
    for (const i of vertices) {
      for (const j of vertices) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

A* Search Algorithm


function aStar(start, goal, heuristic) {
  const openSet = new PriorityQueue();
  openSet.enqueue(start, 0);
  const cameFrom = {};
  const gScore = { [start]: 0 };
  const fScore = { [start]: heuristic(start, goal) };

  while (!openSet.isEmpty()) {
    const current = openSet.dequeue().element;
    
    if (current === goal) {
      return reconstructPath(cameFrom, current);
    }

    for (const neighbor of getNeighbors(current)) {
      const tentativeGScore = gScore[current] + getEdgeWeight(current, neighbor);
      
      if (tentativeGScore < (gScore[neighbor] ?? Infinity)) {
        cameFrom[neighbor] = current;
        gScore[neighbor] = tentativeGScore;
        fScore[neighbor] = tentativeGScore + heuristic(neighbor, goal);
        if (!openSet.contains(neighbor)) {
          openSet.enqueue(neighbor, fScore[neighbor]);
        }
      }
    }
  }
  return null; // No path found
}

Heuristic Tip: Use Manhattan distance for grid worlds

Optimization Techniques:

Bidirectional Search: Run Dijkstra from both start and end
Goal-Directed: A* with landmarks for faster routing
Early Termination: Stop when target is reached
Parallelization: Floyd-Warshall benefits from GPU acceleration

Algorithm Selection Guide

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

4. Real-World Applications

Network Routing

OSPF Protocol: Uses Dijkstra's to calculate shortest paths between routers

// Simplified link-state routing
function calculateRoutingTable(networkTopology) {
  const routerGraph = convertToGraph(networkTopology);
  return dijkstra(routerGraph, 'this-router');
}

Flight Path Optimization

Fuel Efficiency: Bellman-Ford with fuel costs as edge weights

function findCheapestFlight(flightGraph, origin, destination) {
  const { distances } = bellmanFord(flightGraph, origin);
  return distances[destination];
}

Game AI Pathfinding

NPC Movement: A* with terrain cost heuristics

function findGamePath(startTile, targetTile) {
  const heuristic = (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
  return aStar(startTile, targetTile, heuristic);
}

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

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.

0 Interaction

0 Views

0 Likes