Dijkstra's Algorithm: The Shortest Path Finder

Edsger W. Dijkstra

Before diving into the algorithm, let's honor its creator: Edsger W. Dijkstra (1930-2002), a Dutch computer scientist and one of the pioneers of programming as a discipline. His contributions include:

• The Dijkstra's algorithm (1956) for shortest paths
• The banker's algorithm for deadlock avoidance
• Seminal work on structured programming
• The Goto Statement Considered Harmful paper (1968)

Dijkstra's work laid foundations for modern computer science, particularly in algorithm design and programming methodology.

Theory

Key Differences from Unweighted Graphs

To understand this algorithm we first need to understand weighted graphs, I won't go into much details about graphs themselves since I did a blog post which you can find in my blog post on graphs. What I will do is highlight the major difference between them.

Why weights matter: In real-world scenarios, connections often have a weight (distance, time, money). A weighted graph models these relationships more accurately.

Implementation

Core Concepts

1. Priority Queue: Processes nodes based on a weight, smallest or greatest
2. Greedy Approach: Always extends the shortest known path first
3. Relaxation: Updates shorter paths as they're discovered

Visual Example

Consider this graph:

A --2--> B | | 1 | 3 | | C --4--> D

The shortest path from A to D is A→B→D (total weight = 5)

Hands on

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight }); // For undirected graph
  }

  Dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    // Initialize distances and priority queue
    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }

    while (nodes.values.length) {
      smallest = nodes.dequeue().val;

      if (smallest === finish) {
        // Reconstruct path
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest && distances[smallest] !== Infinity) {
        for (let neighbor of this.adjacencyList[smallest]) {
          // Calculate new distance
          let candidate = distances[smallest] + neighbor.weight;
          if (candidate < distances[neighbor.node]) {
            distances[neighbor.node] = candidate;
            previous[neighbor.node] = smallest;
            nodes.enqueue(neighbor.node, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

// Usage Example:
const graph = new WeightedGraph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B", 1);
graph.addEdge("A", "C", 1);
graph.addEdge("B", "D", 3);
graph.addEdge("C", "D", 4);

console.log(graph.Dijkstra("A", "D")); // Output: ["A", "B", "D"]

Explanation:

1. Initialize all distances to Infinity except the start node (distance = 0)
2. Use a priority queue to process nodes by current shortest distance
3. For each node, examine all neighbors and update their distances if a shorter path is found
4. Track the path using a previous object
5. Terminate when the destination node is reached or all nodes are processed

Edge Cases and Limitations

1. Negative Weights: Dijkstra's fails (use Bellman-Ford instead)
2. Disconnected Nodes: Returns empty path if no route exists
3. Tie Breakers: When multiple paths have same weight, returns first found

Practical Use Cases

Dijkstra algorithm is useful in various real-world applications:

• GPS Navigation: Finds fastest routes between locations.
• Network Routing: Determines optimal data paths.
• Airline Scheduling: Calculates most efficient flight connections.
• Game AI: Pathfinding for NPCs.
• Circuit Design: Optimizes wire routing.

Performance Considerations

Time Complexity:

With V being the number of vertices and E the number of edges.

• Naive (array-based): O(V²) mostly suitable for dense graphs
• Binary Heap: O((V+E) log V) most common implementation
• Fibonacci Heap: O(E + V log V) Theoretical best, complex implementation

Space Complexity:

• O(V) for storing distances and previous nodes.
• O(V) for the priority queue.

Conclusion

That's it for Dijkstra's algorithm. I hope you learned as much as I did. If you have any questions or suggestions please hit me up!