Dijkstra’s Algorithm

is one of the most famous algorithms in computer science. It is used to find the shortest path between a starting point and all other destinations in a network (called a Graph) — just like how Google Maps finds the fastest route for your trip.

The Basic Idea

• Start at your location: Set your starting distance to 0 and all other cities to Infinity (∞) because you don’t know the way yet.
• Look at your neighbors: Check the cities directly connected to your current city and calculate the distance to them.
• Always pick the closest path: Choose the nearest unvisited city, move there, and make it your new “current station.”
• Update the scoreboard: From your new station, check its neighbors. If you find a route that is shorter than what you recorded before, erase the old distance and write the new, shorter one.
• Repeat the process until you have visited every single city in the network

The Network Setup (Graph)

We have 3 cities with the following roads and distances:

• From A to B = 4
• From A to C = 2
• From C to B = 1

📋 Step-by-Step Execution

Initially, we set the distance to our starting city (A) to 0, and all other cities to Infinity (∞) because we don’t know the way yet.

Get Emad Mohamed’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

🔴 Step 1: Start at City A

• Current Position: A (Distance = 0)
• Check neighbors of A:
• To City B: Distance is 0 + 4 = 4. (4 is less than ∞, so we update B to 4).
• To City C: Distance is 0 + 2 = 2. (2 is less than ∞, so we update C to 2).
• Current Scoreboard: A: 0 | B: 4 | C: 2
• Next Stop: Choose the unvisited city with the smallest distance, which is C.

🔵 Step 2: Move to City C

• Current Position: C (Distance = 2)
• Check neighbors of C:

To City B: Distance through C is: (Distance to C = 2) + (Road from C to B = 1) = 3.

• Compare & Update: Compare the new distance (3) with the old distance of B (4). Since 3 is shorter, we update B to 3.
• Current Scoreboard: A: 0 | B: 3 | C: 2
• Next Stop: Choose the remaining unvisited city, which is B.

🟢 Step 3: Move to City B

• Current Position: B (Distance = 3)
• Check neighbors of B: B has no outgoing roads to unvisited cities.
• Finish: All cities have been visited!

🏆 Final Shortest Path Result

The algorithm successfully found the absolute smartest paths from A:

JavaScript code to print these steps :

function dijkstra(graph, start) {
    // Scoreboard to keep track of the shortest distance to each city
    let distances = {};
    
    // Set to keep track of all visited cities
    let visited = new Set();

    // Step 1: Initialize all distances to Infinity, except the start city (0)
    for (let city in graph) {
        distances[city] = Infinity;
    }
    distances[start] = 0; 

    while (true) {
        // Step 2: Find the unvisited city with the smallest known distance
        let currentCity = null;
        let shortestDistance = Infinity;

        for (let city in distances) {
            if (!visited.has(city) && distances[city] < shortestDistance) {
                shortestDistance = distances[city];
                currentCity = city;
            }
        }

        // If no more reachable cities are found, stop the loop
        if (currentCity === null) break;

        // Step 3: Check neighbors of the current city and update distances
        let neighbors = graph[currentCity];
        for (let neighbor in neighbors) {
            let roadWeight = neighbors[neighbor];
            let newDistance = distances[currentCity] + roadWeight;

            // If the new path is shorter, update the scoreboard
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
            }
        }

        // Step 4: Mark the current city as visited
        visited.add(currentCity);
    }

    return distances;
}

// --- Testing our graph example ---

const map = {
    A: { B: 4, C: 2 },
    B: {},
    C: { B: 1 }
};

// Run the algorithm starting from city 'A'
const shortestPaths = dijkstra(map, 'A');

console.log(shortestPaths); 
// Output: { A: 0, B: 3, C: 2 }