Shortest Path Algorithms (Dijkstra)

Dijkstra’s algorithm is a graph algorithm used to find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It is one of the most widely used shortest-path algorithms in practice.

Dijkstra’s algorithm works by repeatedly selecting the vertex with the smallest known distance and relaxing its outgoing edges.

When to Use Dijkstra’s Algorithm

Dijkstra’s algorithm is appropriate when:

• The graph is weighted
• All edge weights are non-negative
• Shortest paths from a single source are required

It does not work correctly with negative edge weights.

Key Idea

The algorithm maintains:

• A distance table storing the shortest known distance from the source
• A priority queue (min-heap) to always process the closest unvisited vertex next

At each step:

1. Pick the vertex with the smallest tentative distance
2. Update (relax) distances to its neighbors
3. Repeat until all vertices are processed

Example Graph

Weighted directed graph:

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

Starting from A, the shortest paths are:

• A → B = 1
• A → B → D = 3
• A → B → E = 2

Dijkstra’s Algorithm Steps

1. Initialize all distances to infinity

2. Set the source distance to 0

3. Push the source into a min-priority queue

4. While the queue is not empty:

   • Extract the vertex with the smallest distance
   • Relax all outgoing edges

5. Final distances represent shortest paths

Graph Representation

This implementation uses an adjacency list where each edge stores a (neighbor, weight) pair.

Rust Implementation

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

type Graph = HashMap<i32, Vec<(i32, i32)>>;

pub fn dijkstra(graph: &Graph, start: i32) -> HashMap<i32, i32> {
    let mut distances = HashMap::new();
    let mut heap = BinaryHeap::new();

    for &node in graph.keys() {
        distances.insert(node, i32::MAX);
    }

    distances.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((current_dist, node))) = heap.pop() {
        if current_dist > distances[&node] {
            continue;
        }

        if let Some(neighbors) = graph.get(&node) {
            for &(neighbor, weight) in neighbors {
                let new_dist = current_dist + weight;

                if new_dist < distances[&neighbor] {
                    distances.insert(neighbor, new_dist);
                    heap.push(Reverse((new_dist, neighbor)));
                }
            }
        }
    }

    distances
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![(2, 1), (3, 4)]);
    graph.insert(2, vec![(3, 1), (4, 2)]);
    graph.insert(3, vec![(4, 3)]);
    graph.insert(4, vec![]);

    let distances = dijkstra(&graph, 1);

    for (node, dist) in distances {
        println!("Distance from 1 to {} = {}", node, dist);
    }
}

Output:

Distance from 1 to 1 = 0
Distance from 1 to 2 = 1
Distance from 1 to 3 = 2
Distance from 1 to 4 = 3

Time and Space Complexity

Time Complexity

Space Complexity

Limitations of Dijkstra’s Algorithm

• Does not support negative edge weights
• Does not detect negative cycles
• Requires all weights ≥ 0

For graphs with negative weights, algorithms like Bellman-Ford should be used.

Summary

• Dijkstra’s algorithm finds shortest paths from a single source
• Uses a greedy strategy with a priority queue
• Efficient and widely used in practice
• Works only with non-negative edge weights

Playground Links

Rust - Dijkstra’s Algorithm