An Illustrated Guide to Dijkstra's Algorithm

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Introduction

In this lesson, we will learn about `Dijkstra's algorithm`, with a focus on following key points: 1. What is Dijkstra's Algorithm? 2. What are shortest path problems? 3. See a working implementation of Djikstra's algorithm in Python

The field of computer science encompasses a wide variety of problems. The shortest path problem is an important one, and we see many applications of it daily.

For example, we often need to find the shortest path between two points while traveling. Web mapping applications such as Google Maps use these algorithms to display the shortest routes.

The shortest path problem can be solved using different algorithms, such as Breadth-First Search (BFS), A* search algorithm, or Floyd-Warshall algorithm. However, the most popular and optimal shortest path algorithm is the Dijkstra's algorithm.

Problem Representation

Shortest path problems are represented in the form of a graph. Before moving forward, let's review our knowledge of graph concepts.

Multiple Choice

A graph consists of ____ and _____.

Problem Representation 2

For shortest path problems, nodes represent cities (or points) and the edges represent the connectivity, or connection, from one node to another, as illustrated below. These types of problems may have one or more source nodes from which paths are determined. This problem can be both represented using either directed or undirected graphs.

Time for another review question!

Multiple Choice

Directed graphs are ____ and undirected graphs are ____.

Algorithm

Now that we've established the problem representation, let's discuss Dijkstra's algorithm. Dijkstra's requires the input graph to have only one source node. It also requires that all the edges in the graph have non-negative weights.

Suppose we are given a map such as the one below and wish to travel from city A to city F. In a simple graph like this, we can see that there are several paths to travel from A to F.

After a hard look, you'll realize that the path A -> C -> D -> F will give us the shortest path. But that required a lot of thought, and you most likely had to analyze every path one by one before coming to the conclusion.

But what if you have a more complicated graph with hundreds of cities? In such a case, you could use Dijkstra's algorithm. It makes this work easier by finding the distance values for the path for each unvisited node n. This distance value will be the shortest distance of that node n from the source node. This helps in determining the shortest path.

First-step

Let's dive deep into the algorithm by initializing some variables that are required for Dijkstra's algorithm. We'll need the following:

A list of all unvisited nodes in the graph.
A list of distances with their nodes in the graph. At first, the distance of all the nodes is initialized as infinity, except the source node (which is initialized as 0).
A list of all nodes that are visited, and which make the shortest path. At first, this list will contain the source node only.

The algorithm starts from the source node, which in this case is A. We change the distances of nodes B and C in the distance list to be 5 and 2. As the sum of distance value from source node to nodes B and C is greater than the original distance, they are changed. The graph and the corresponding lists look as illustrated below.

Second Step

We now move towards the unvisited node with smallest distance, which is node C. The distances of nodes D and E are now updated to 6 and 10.

As the sum of the distance from the source node to nodes D and E is greater than the original distance, this was updated.

In the case of node D, the distance of A to C is 2, and C to D is 4. As such, the total distance from source node for D became 2 + 4 = 6.

Node E was updated in the same manner. Since C gives the shortest path so far, it is added to the shortest path. The changes are implemented as illustrated below.

Third Step

The unvisited node with smallest distance value is now B. Since visiting B does not open any new paths, the distance values of nodes remain unchanged, and it is also not added to the path. B now moves to the visited node list.

Fourth Step

Now, D is the unvisited node with the smallest distance value. By visiting node D, we find a new connection F and update its distance value to 2 + 4 + 4 = 10. This is added to the shortest path as node D gives shortest path from the previous node C.

Fifth Step

Now node E and F have similar distance values. Proceeding in lexicographic order, we will visit node E first. This does not add to the shortest path and does not change the distance values of nodes either.

Final Step

The last node to visit is F, which is also our destination node. The shortest path is now completed by adding the path from node D to F. The total weight of this shortest path is 10. All other paths that lead to the destination node F will give a larger distance than 10.

Now that we've seen an illustrative example, let's think a little more about the algorithm.

True or False

Can Dijkstra's algorithm work on both directed and undirected graphs?

Implementation

The direction of edges is not important in Dijkstra's algorithm. As long as the input graph is in proper format, the algorithm will give the correct output path.

Implementation

Let's implement this algorithm. You can represent the graph in different ways, but for this tutorial, we will represent it as an adjacency list (in the form of nested dictionaries).

For this implementation, we have the source node, destination node, and the example graph is represented as:

graph = {'a':{'b':5,'c':2},
        'b':{'a':5,'c':7,'d':8},     
        'c':{'a':2,'b':7,'d':4,'e':8},
        'd':{'b':8,'c':4,'e':6, 'f':4},
        'e':{'c':8,'d':6,'f':3}, 
        'f':{'e':3, 'd':4}}

source = 'a'
destination = 'f'

const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};

HashMap<String, HashMap<String, Integer>> graph = new HashMap<String, HashMap<String, Integer>>() {{
    put("a", new HashMap<String, Integer>() {{
        put("b", 5);
        put("c", 2);
    }});
    put("b", new HashMap<String, Integer>() {{
        put("a", 5);
        put("c", 7);
        put("d", 8);
    }});
    put("c", new HashMap<String, Integer>() {{
        put("a", 2);
        put("b", 7);
        put("d", 4);
        put("e", 8);
    }});
    put("d", new HashMap<String, Integer>() {{
        put("b", 8);
        put("c", 4);
        put("e", 6);
        put("f", 4);
    }});
    put("e", new HashMap<String, Integer>() {{
        put("c", 8);
        put("d", 6);
        put("f", 3);
    }});
    put("f", new HashMap<String, Integer>() {{
        put("e", 3);
        put("d", 4);
    }});
}};

String source = "a";
String destination = "f";

Dictionary<string, Dictionary<string, int>> graph = new Dictionary<string, Dictionary<string, int>>
{
 {"a", new Dictionary<string, int> { { "b", 5 }, { "c", 2 } }},
 {"b", new Dictionary<string, int> { { "a", 5 }, { "c", 7 }, { "d", 8 } }},
 {"c", new Dictionary<string, int> { { "a", 2 }, { "b", 7 }, { "d", 4 }, { "e", 8 } }},
 {"d", new Dictionary<string, int> { { "b", 8 }, { "c", 4 }, { "e", 6 }, { "f", 4 } }},
 {"e", new Dictionary<string, int> { { "c", 8 }, { "d", 6 }, { "f", 3 } }},
 {"f", new Dictionary<string, int> { { "e", 3 }, { "d", 4 } }}
};

string source = "a";
string destination = "f";

std::map<std::string, std::map<std::string, int>> graph = {
    {"a", {{"b", 5}, {"c", 2}}},
    {"b", {{"a", 5}, {"c", 7}, {"d", 8}}},
    {"c", {{"a", 2}, {"b", 7}, {"d", 4}, {"e", 8}}},
    {"d", {{"b", 8}, {"c", 4}, {"e", 6}, {"f", 4}}},
    {"e", {{"c", 8}, {"d", 6}, {"f", 3}}},
    {"f", {{"e", 3}, {"d", 4}}}
};

std::string source = "a";
std::string destination = "f";

graph := map[string]map[string]int{
    "a": {"b": 5, "c": 2},
    "b": {"a": 5, "c": 7, "d": 8},
    "c": {"a": 2, "b": 7, "d": 4, "e": 8},
    "d": {"b": 8, "c": 4, "e": 6, "f": 4},
    "e": {"c": 8, "d": 6, "f": 3},
    "f": {"e": 3, "d": 4},
}

source := "a"
destination := "f"

Graph As Neighbor Maps

Before the loop starts, make sure the input shape is clear: each node points to a small map of its neighbors, and each neighbor stores the edge weight.

In this example, reading a -> {b: 5, c: 2} means: from a, we can reach b with cost 5 or c with cost 2. Dijkstra repeatedly reads exactly this local neighbor information.

Graph As Neighbor Maps

Adjacency List Shape

Before diving into the implementation details, make sure the input shape is clear.

Each key is a node. Each nested key-value pair says: “from this node, I can reach this neighbor with this edge cost.” For an undirected graph, the same edge appears in both directions.

Adjacency List Shape

Implementation Step 2

Now the unvisited, path, and distance lists of nodes are initialized. All the initial distance values of all nodes are set to infinity except the source node which is zero.

```py
import math

graph = {'a':{'b':5,'c':2},
        'b':{'a':5,'c':7,'d':8},     
        'c':{'a':2,'b':7,'d':4,'e':8},
        'd':{'b':8,'c':4,'e':6, 'f':4},
        'e':{'c':8,'d':6,'f':3}, 
        'f':{'e':3, 'd':4}}

source = 'a'
destination = 'f'

unvisited = graph
shortest_distances = {}
route = [] 
path_nodes = {}

for nodes in unvisited:
   shortest_distances[nodes] = math.inf
# set distance of source to 0
shortest_distances[source] = 0
```
```js
const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};

const formatGraph = (g) => {
  const tmp = {};
  Object.keys(g).forEach((k) => {
    const obj = g[k];
    const arr = [];
    Object.keys(obj).forEach((v) => arr.push({ vertex: v, cost: obj[v] }));
    tmp[k] = arr;
  });
  return tmp;
};

const dijkstra = (graph, start, end) => {
  var map = formatGraph(graph);

  var visited = [];
  var unvisited = [start];
  // set distance of source to 0
  var shortestDistances = { [start]: { vertex: start, cost: 0 } };
}
```
```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        Map<String, Integer> a = new HashMap<>(); a.put("b", 5); a.put("c", 2); graph.put("a", a);
        Map<String, Integer> b = new HashMap<>(); b.put("a", 5); b.put("c", 7); b.put("d", 8); graph.put("b", b);
        Map<String, Integer> c = new HashMap<>(); c.put("a", 2); c.put("b", 7); c.put("d", 4); c.put("e", 8); graph.put("c", c);
        Map<String, Integer> d = new HashMap<>(); d.put("b", 8); d.put("c", 4); d.put("e", 6); d.put("f", 4); graph.put("d", d);
        Map<String, Integer> e = new HashMap<>(); e.put("c", 8); e.put("d", 6); e.put("f", 3); graph.put("e", e);
        Map<String, Integer> f = new HashMap<>(); f.put("e", 3); f.put("d", 4); graph.put("f", f);
        String source = "a", destination = "f";
        Map<String, Integer> unvisited = graph;
        Map<String, Integer> shortestDistances = new HashMap<>();
        List<String> route = new ArrayList<>();
        Map<String, String> pathNodes = new HashMap<>();
        unvisited.forEach((key, val) -> shortestDistances.put(key, Integer.MAX_VALUE));
        // set distance of source to 0
        shortestDistances.put(source, 0);
    }
}
```
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, map<string, int>> graph = {
        {"a", {{"b", 5}, {"c", 2}}},
        {"b", {{"a", 5}, {"c", 7}, {"d", 8}}},
        {"c", {{"a", 2}, {"b", 7}, {"d", 4}, {"e", 8}}},
        {"d", {{"b", 8}, {"c", 4}, {"e", 6}, {"f", 4}}},
        {"e", {{"c", 8}, {"d", 6}, {"f", 3}}},
        {"f", {{"e", 3}, {"d", 4}}}
    };
    string source = "a", destination = "f";
    map<string, int> shortestDistances;
    vector<string> route;
    map<string, string> pathNodes;
    for(auto& node : graph) shortestDistances[node.first] = INT_MAX;
    // set distance of source to 0
    shortestDistances[source] = 0;
}
```
```csharp
using System;
using System.Linq;
using System.Collections.Generic;

public class MainClass
{
    public static void Main()
    {
        Dictionary<string, Dictionary<string, int>> graph = new Dictionary<string, Dictionary<string, int>>() {
            {"a", new Dictionary<string, int>(){ {"b", 5}, {"c", 2} }},
            {"b", new Dictionary<string, int>(){ {"a", 5}, {"c", 7}, {"d", 8} }},
            {"c", new Dictionary<string, int>(){ {"a", 2}, {"b", 7}, {"d", 4}, {"e", 8} }},
            {"d", new Dictionary<string, int>(){ {"b", 8}, {"c", 4}, {"e", 6}, {"f", 4} }},
            {"e", new Dictionary<string, int>(){ {"c", 8}, {"d", 6}, {"f", 3} }},
            {"f", new Dictionary<string, int>(){ {"e", 3}, {"d", 4} }},
        };
        string source = "a", destination = "f";
        Dictionary<string, int> shortestDistances = new Dictionary<string, int>();
        List<string> route = new List<string>();
        Dictionary<string, string> pathNodes = new Dictionary<string, string>();
        foreach(var node in graph) shortestDistances[node.Key] = Int32.MaxValue;
        // set distance of source to 0
        shortestDistances[source] = 0;
    }
}
```
```go
package main

import "fmt"
import "math"

func main() {
    graph := map[string]map[string]float64{
        "a": {"b": 5, "c": 2},
        "b": {"a": 5, "c": 7, "d": 8},
        "c": {"a": 2, "b": 7, "d": 4,"e": 8},
        "d": {"b": 8, "c": 4, "e": 6, "f": 4},
        "e": {"c": 8, "d": 6, "f": 3},
        "f": {"e": 3, "d": 4},
    }
    source, destination := "a", "f"
    shortestDistances := make(map[string]float64)
    pathNodes := make(map[string]string)
    for node, _ := range graph {
        shortestDistances[node] = math.Inf(1)
    }
    // set distance of source to 0
    shortestDistances[source] = 0
}
```

Initial State Checklist

At initialization, Dijkstra separates the problem into three pieces of state:

unvisited: nodes we have not finalized yet
shortest_distances: best known cost from the source
path_nodes: previous node used to rebuild the route later

The key idea: only the source starts at 0; every other node starts as unknown, so its distance is ∞.

Initial State Checklist

Initial Dijkstra State

At the start, Dijkstra knows only one fact with certainty: the distance from the source to itself is 0.

Every other node starts at ∞ because no route has been discovered yet. The algorithm will replace those values as it finds cheaper paths.

Initial Dijkstra State

Implementation Step 3

This is the main part of the algorithm. An unvisited node with the shortest distance from the source node is selected. All the neighboring nodes from that node are then checked, and distances are updated. Nodes are added to the path list whenever the distance is updated. This process is repeated until all the nodes in the graph are visited.

```py
import math

graph = {'a':{'b':5,'c':2},
        'b':{'a':5,'c':7,'d':8},     
        'c':{'a':2,'b':7,'d':4,'e':8},
        'd':{'b':8,'c':4,'e':6, 'f':4},
        'e':{'c':8,'d':6,'f':3}, 
        'f':{'e':3, 'd':4}}

source = 'a'
destination = 'f'

unvisited = graph
shortest_distances = {}
route = [] 
path_nodes = {}

for nodes in unvisited:
   shortest_distances[nodes] = math.inf
shortest_distances[source] = 0

while(unvisited):
       min_node = None
       for current_node in unvisited: 
           if min_node is None:
               min_node = current_node        
           elif shortest_distances[min_node] > shortest_distances[current_node]:
               min_node = current_node
       for node,value in unvisited[min_node].items():
           if value + shortest_distances[min_node] < shortest_distances[node]:  
               shortest_distances[node] = value + shortest_distances[min_node]
               path_nodes[node] = min_node
       unvisited.pop(min_node)

```
```cpp
#include <map>
#include <string>
#include <limits>
#include <vector>

std::map<std::string, std::map<std::string, int>> graph = {{"a",{{"b",5},{"c",2}}},
                                                           {"b",{{"a",5},{"c",7},{"d",8}}},
                                                           {"c",{{"a",2},{"b",7},{"d",4},{"e",8}}},
                                                           {"d",{{"b",8},{"c",4},{"e",6}, {"f",4}}},
                                                           {"e",{{"c",8},{"d",6},{"f",3}}},
                                                           {"f",{{"e",3}, {"d",4}}
                                                          }};

std::string source = "a";
std::string destination = "f";

std::map<std::string, std::map<std::string, int>> unvisited = graph;
std::map<std::string, int> shortest_distances;
std::vector<std::string> route;
std::map<std::string, std::string> path_nodes;

// Initialize shortest distances to infinity for each node
for (std::map<std::string, std::map<std::string, int>>::iterator it = unvisited.begin(); it != unvisited.end(); it++) {
       shortest_distances[it->first] = std::numeric_limits<int>::max();
}
shortest_distances[source] = 0;

while(!unvisited.empty()){
       std::string min_node = "";
       // Select a node with the minimum path length
       for (std::map<std::string, int>::iterator it = shortest_distances.begin(); it != shortest_distances.end(); it++) {
           if (min_node == "" || shortest_distances[min_node] > it->second) min_node = it->first;
       }
       // Update the shortest path values based on the selected node
       for (std::map<std::string, int>::iterator it = unvisited[min_node].begin(); it != unvisited[min_node].end(); it++) {
           if (it->second + shortest_distances[min_node] < shortest_distances[it->first]) {
               shortest_distances[it->first] = it->second + shortest_distances[min_node];
               path_nodes[it->first] = min_node;
           }
       }
       // Remove the selected node from the graph
       unvisited.erase(min_node);
}
```
```js
const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};

const formatGraph = (g) => {
  const tmp = {};
  Object.keys(g).forEach((k) => {
    const obj = g[k];
    const arr = [];
    Object.keys(obj).forEach((v) => arr.push({ vertex: v, cost: obj[v] }));
    tmp[k] = arr;
  });
  return tmp;
};

const dijkstra = (graph, start, end) => {
  var map = formatGraph(graph);

  var visited = [];
  var unvisited = [start];
  var shortestDistances = { [start]: { vertex: start, cost: 0 } };

  var vertex;
  while ((vertex = unvisited.shift())) {
    // Explore unvisited neighbors
    var neighbors = map[vertex].filter((n) => !visited.includes(n.vertex));

    // Add neighbors to the unvisited list
    unvisited.push(...neighbors.map((n) => n.vertex));

    var costToVertex = shortestDistances[vertex].cost;

    for (let { vertex: to, cost } of neighbors) {
      var currCostToNeighbor =
        shortestDistances[to] && shortestDistances[to].cost;
      var newCostToNeighbor = costToVertex + cost;
      if (
        currCostToNeighbor == undefined ||
        newCostToNeighbor < currCostToNeighbor
      ) {
        // Update the table
        shortestDistances[to] = { vertex, cost: newCostToNeighbor };
      }
    }

    visited.push(vertex);
  }
}
```
```java
import java.util.*;

public class Main {

    public static void main(String[] args) {
        HashMap<String, HashMap<String, Integer>> graph = new HashMap<String, HashMap<String, Integer>>();
        graph.put("a", new HashMap<String, Integer>() {{
            put("b", 5);
            put("c", 2);
        }});
        graph.put("b", new HashMap<String, Integer>() {{
            put("a", 5);
            put("c", 7);
            put("d", 8);
        }});
        graph.put("c", new HashMap<String, Integer>() {{
            put("a", 2);
            put("b", 7);
            put("d", 4);
            put("e", 8);
        }});
        graph.put("d", new HashMap<String, Integer>() {{
            put("b", 8);
            put("c", 4);
            put("e", 6);
            put("f", 4);
        }});
        graph.put("e", new HashMap<String, Integer>() {{
            put("c", 8);
            put("d", 6);
            put("f", 3);
        }});
        graph.put("f", new HashMap<String, Integer>() {{
            put("e", 3);
            put("d", 4);
        }});

        String source = "a";
        String destination = "f";

        HashMap<String, Integer> shortestDistances = new HashMap<>();
        HashMap<String, String> pathNodes = new HashMap<>();

        for (String node : graph.keySet())
            shortestDistances.put(node, Integer.MAX_VALUE);
        shortestDistances.replace(source, 0);

        while (!graph.isEmpty()) {
            String minNode = null;
            for (String node : graph.keySet())
                if (minNode == null || shortestDistances.get(minNode) > shortestDistances.get(node))
                    minNode = node;

            for (Map.Entry<String, Integer> entry : graph.get(minNode).entrySet())
                if (entry.getValue() + shortestDistances.get(minNode) < shortestDistances.get(entry.getKey())) {
                    shortestDistances.replace(entry.getKey(), entry.getValue() + shortestDistances.get(minNode));
                    pathNodes.put(entry.getKey(), minNode);
                }

            graph.remove(minNode);
        }
    }
}
```
```csharp
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, Dictionary<string, int>> graph = new Dictionary<string, Dictionary<string, int>>()
        {
            {"a", new Dictionary<string, int>{{"b", 5},{"c", 2}}},
            {"b", new Dictionary<string, int>{{"a", 5},{"c", 7},{"d", 8}}},
            {"c", new Dictionary<string, int>{{"a", 2},{"b", 7},{"d", 4},{"e", 8}}},
            {"d", new Dictionary<string, int>{{"b", 8},{"c", 4},{"e", 6},{"f", 4}}},
            {"e", new Dictionary<string, int>{{"c", 8},{"d", 6}, {"f", 3}}},
            {"f", new Dictionary<string, int>{{"e", 3},{"d", 4}}},
        };

        string source = "a";
        string destination = "f";

        Dictionary<string, int> shortestDistances = new Dictionary<string, int>();
        Dictionary<string, string> pathNodes = new Dictionary<string, string>();

        foreach (string node in graph.Keys)
            shortestDistances[node] = int.MaxValue;
        shortestDistances[source] = 0;

        while (graph.Count > 0)
        {
            string minNode = null;

            foreach (string node in graph.Keys)
                if (minNode == null || shortestDistances[minNode] > shortestDistances[node])
                    minNode = node;

            foreach (KeyValuePair<string, int> node in graph[minNode])
                if (node.Value + shortestDistances[minNode] < shortestDistances[node.Key])
                {
                    shortestDistances[node.Key] = node.Value + shortestDistances[minNode];
                    pathNodes[node.Key] = minNode;
                }

            graph.Remove(minNode);
        }
    }
}
```
```go
package main

import "fmt"

const inf = int(^uint(0) >> 1)

func main() {
    graph := map[string]map[string]int{
        "a": {"b": 5, "c": 2},
        "b": {"a": 5, "c": 7, "d": 8},
        "c": {"a": 2, "b": 7, "d": 4, "e": 8},
        "d": {"b": 8, "c": 4, "e": 6, "f": 4},
        "e": {"c": 8, "d": 6, "f": 3},
        "f": {"e": 3, "d": 4},
    }

    source := "a"
    destination := "f"

    shortestDistances := make(map[string]int)
    pathNodes := make(map[string]string)

    for node := range graph {
        shortestDistances[node] = inf
    }
    shortestDistances[source] = 0

	for len(graph) > 0 {
		minNode := ""
		minVal := inf
		for node := range graph {
			if shortestDistances[node] < minVal {
				minVal = shortestDistances[node]
				minNode = node
			}
		}
		for neighbor, value := range graph[minNode] {
			alternativeValue := shortestDistances[minNode] + value
			if alternativeValue < shortestDistances[neighbor] {
				shortestDistances[neighbor] = alternativeValue
				pathNodes[neighbor] = minNode
			}
		}
		delete(graph, minNode)
	}
}
```

Relaxation Decision

The core update is called relaxation. For each neighbor, Dijkstra asks one question:

Is the route through the current node cheaper than what we already know?

If yes, update the neighbor's distance and remember the current node as its predecessor. If no, leave the state unchanged.

Relaxation Decision

Relaxation Loop Snapshot

The core loop repeats the same move: pick the unvisited node with the smallest known distance, then try to improve its neighbors.

This “try to improve” step is called relaxation. If current distance + edge weight is cheaper than the neighbor's saved distance, update the distance and remember the current node as the predecessor.

Relaxation Loop Snapshot

Implementation Step 4

To get the shortest path, we also check if it is possible to reach the destination node from the source node, as there is a possibility that it may not be reachable. The destination node is then added to the list of routes which gives us the shortest path.

```py
graph = {
  'a': {'b': 5, 'c': 2 },
  'b': {'a': 5, 'c': 7, 'd': 8 },
  'c': {'a': 2, 'b': 7, 'd': 4, 'e': 8 },
  'd': {'b': 8, 'c': 4, 'e': 6, 'f': 4 },
  'e': {'c': 8, 'd': 6, 'f': 3 },
  'f': {'e': 3, 'd': 4 },
}


def print_table(table):
    return "\n".join([f"{vertex}: {table[vertex]['cost']} via {table[vertex]['vertex']}" for vertex in table.keys()])


def trace_path(table, start, end):
    path = []
    next = end
    while True:
        path.insert(0, next)
        if next == start:
            break
        next = table[next]['vertex']
    
    return path


def format_graph(g):
    tmp = {}
    for k in g.keys():
        obj = g[k]
        arr = [{'vertex': v, 'cost': obj[v]} for v in obj.keys()]
        tmp[k] = arr
    return tmp


def dijkstra(graph, start, end):
    map = format_graph(graph)

    visited = []
    unvisited = [start]
    shortest_distances = {start: {'vertex': start, 'cost': 0}}

    while unvisited:
        vertex = unvisited.pop(0)

        # Explore unvisited neighbors
        neighbors = [n for n in map[vertex] if n['vertex'] not in visited]

        # Add neighbors to the unvisited list
        unvisited.extend([n['vertex'] for n in neighbors])

        cost_to_vertex = shortest_distances[vertex]['cost']

        for neighbor in neighbors:
            vertex_to = neighbor['vertex']
            cost = neighbor['cost']
            curr_cost_to_neighbor = shortest_distances.get(vertex_to, {}).get('cost')
            new_cost_to_neighbor = cost_to_vertex + cost
            if curr_cost_to_neighbor is None or new_cost_to_neighbor < curr_cost_to_neighbor:
                # Update the table
                shortest_distances[vertex_to] = {'vertex': vertex, 'cost': new_cost_to_neighbor}

        visited.append(vertex)

    print("Table of costs:")
    print(print_table(shortest_distances))

    path = trace_path(shortest_distances, start, end)

    print("Shortest path is: ", " -> ".join(path), " with weight ", shortest_distances[end]['cost'])


dijkstra(graph, "a", "f")
```
```cpp
#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <limits>

using namespace std;

struct Edge {
    string to;
    int weight;
};

using Graph = map<string, vector<Edge>>;

struct TableRow {
    string vertex;
    int cost;
};

using Table = map<string, TableRow>;

Graph formatGraph(map<string, map<string, int>> g) {
    Graph formatted;
    for (auto& kv : g) {
        string vertex = kv.first;
        vector<Edge> edges;
        for (auto& edge : kv.second) {
            edges.push_back({edge.first, edge.second});
        }
        formatted[vertex] = edges;
    }
    return formatted;
}

Table dijkstra(Graph graph, string start, string end) {
    deque<string> unvisited {start};
    Table shortestDistances;
    shortestDistances[start] = {start, 0};

    string vertex;
    while (!unvisited.empty()) {
        vertex = unvisited.front();
        unvisited.pop_front();

        vector<Edge> neighbors;
        copy_if(begin(graph[vertex]), end(graph[vertex]), back_inserter(neighbors),
            [&shortestDistances](Edge n){
                return shortestDistances.find(n.to) == shortestDistances.end();
            });

        for (auto neighbor : neighbors) unvisited.push_back(neighbor.to);

        int costToVertex = shortestDistances[vertex].cost;

        for (Edge edge : neighbors) {
            int currCostToNeighbor = numeric_limits<int>::max();
            if (shortestDistances.find(edge.to) != shortestDistances.end()) {
                currCostToNeighbor = shortestDistances[edge.to].cost;
            }
            int newCostToNeighbor = costToVertex + edge.weight;
            if (newCostToNeighbor < currCostToNeighbor) {
                shortestDistances[edge.to] = { vertex, newCostToNeighbor };
            }
        }
    }

    return shortestDistances;
}

deque<string> tracePath(Table table, string start, string end) {
    deque<string> path;
    string next = end;

    while (true) {
        path.push_front(next);
        if (next == start) break;
        next = table[next].vertex;
    }

    return path;
}

void printTable(Table table) {
    for (auto& kv : table) {
        cout << kv.first << ": " << kv.second.cost << " via " << kv.second.vertex << "\n";
    }
}

int main() {
    map<string, map<string, int>> initial_graph = {
        {"a", {{"b", 5}, {"c", 2}}},
        {"b", {{"a", 5}, {"c", 7}, {"d", 8}}},
        {"c", {{"a", 2}, {"b", 7}, {"d", 4}, {"e", 8}}},
        {"d", {{"b", 8}, {"c", 4}, {"e", 6}, {"f", 4}}},
        {"e", {{"c", 8}, {"d", 6}, {"f", 3}}},
        {"f", { {"e", 3}, {"d", 4} }},
    };

    auto graph = formatGraph(initial_graph);
    auto start = "a";
    auto end   = "f";

    auto table = dijkstra(graph, start, end);
    cout << "Table of costs:\n";
    printTable(table);

    auto path = tracePath(table, start, end);
    cout << "Shortest path is: ";
    for (auto& v : path) cout << v << " -> ";
    cout << "\b\b\b\b\b\b";
    cout << " with weight " << table[end].cost << "\n";

    return 0;
}
```
```js
const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};

const printTable = (table) => {
  return Object.keys(table)
    .map((vertex) => {
      var { vertex: from, cost } = table[vertex];
      return `${vertex}: ${cost} via ${from}`;
    })
    .join("\n");
};

const tracePath = (table, start, end) => {
  var path = [];
  var next = end;
  while (true) {
    path.unshift(next);
    if (next === start) {
      break;
    }
    next = table[next].vertex;
  }

  return path;
};

const formatGraph = (g) => {
  const tmp = {};
  Object.keys(g).forEach((k) => {
    const obj = g[k];
    const arr = [];
    Object.keys(obj).forEach((v) => arr.push({ vertex: v, cost: obj[v] }));
    tmp[k] = arr;
  });
  return tmp;
};

const dijkstra = (graph, start, end) => {
  var map = formatGraph(graph);

  var visited = [];
  var unvisited = [start];
  var shortestDistances = { [start]: { vertex: start, cost: 0 } };

  var vertex;
  while ((vertex = unvisited.shift())) {
    // Explore unvisited neighbors
    var neighbors = map[vertex].filter((n) => !visited.includes(n.vertex));

    // Add neighbors to the unvisited list
    unvisited.push(...neighbors.map((n) => n.vertex));

    var costToVertex = shortestDistances[vertex].cost;

    for (let { vertex: to, cost } of neighbors) {
      var currCostToNeighbor =
        shortestDistances[to] && shortestDistances[to].cost;
      var newCostToNeighbor = costToVertex + cost;
      if (
        currCostToNeighbor == undefined ||
        newCostToNeighbor < currCostToNeighbor
      ) {
        // Update the table
        shortestDistances[to] = { vertex, cost: newCostToNeighbor };
      }
    }

    visited.push(vertex);
  }

  console.log("Table of costs:");
  console.log(printTable(shortestDistances));

  const path = tracePath(shortestDistances, start, end);

  console.log(
    "Shortest path is: ",
    path.join(" -> "),
    " with weight ",
    shortestDistances[end].cost
  );
};

dijkstra(graph, "a", "f");
```
```java
Map<String, Integer> shortestDistances = new HashMap<>();
Map<String, Integer> pathNodes = new HashMap<>();
List<String> unvisited = new ArrayList<>(graph.keySet());
List<String> route = new ArrayList<>();

for (String node : unvisited) {
    shortestDistances.put(node, Integer.MAX_VALUE);
}
shortestDistances.replace(source, 0);

while (!unvisited.isEmpty()) {
    String minNode = null;
    for (String node : unvisited) {
        if (minNode == null || shortestDistances.get(minNode) > shortestDistances.get(node)) {
            minNode = node;
        }
    }
    
    for (Map.Entry<String, Integer> entry : unvisited.get(minNode).entrySet()) {
        String node = entry.getKey();
        int value = entry.getValue();
        if (value + shortestDistances.get(minNode) < shortestDistances.get(node)) {
            shortestDistances.replace(node, value + shortestDistances.get(minNode));
            pathNodes.replace(node, minNode);
        }
    }
    unvisited.remove(minNode);
    
    String node = destination;
    while (node != source) {
        try {
            route.add(0, node);
            node = pathNodes.get(node);
        } catch (Exception e) {
            System.out.print("Path not reachable");
            break;
        }
    }
    route.add(0, source);
}
```
```csharp
var shortestDistances = new Dictionary<string, int>();
var pathNodes = new Dictionary<string, string>();
var unvisited = new List<string>(graph.Keys);
var route = new List<string>();

foreach (var node in unvisited)
{
    shortestDistances[node] = int.MaxValue;
}
shortestDistances[source] = 0;

while (unvisited.Count > 0)
{
    string minNode = null;
    foreach (var node in unvisited)
    {
        if (minNode == null || shortestDistances[minNode] > shortestDistances[node])
        {
            minNode = node;
        }
    }

    foreach (var entry in graph[minNode])
    {
        var node = entry.Key;
        var value = entry.Value;
        if (value + shortestDistances[minNode] < shortestDistances[node])
        {
            shortestDistances[node] = value + shortestDistances[minNode];
            pathNodes[node] = minNode;
        }
    }
    unvisited.Remove(minNode);
    var node = destination;
    while (node != source)
    {
        try
        {
            route.Insert(0, node);
            node = pathNodes[node];
        }
        catch (Exception)
        {
            Console.WriteLine("Path not reachable");
            break;
        }
    }
    route.Insert(0, source);
}
```
```go
shortestDistances := make(map[string]int)
pathNodes := make(map[string]string)
unvisited := make([]string, len(graph))
copy(unvisited, graph)

for _, node := range unvisited {
    shortestDistances[node] = math.MaxInt32
}
shortestDistances[source] = 0

for len(unvisited) > 0 {
    minNode := ""
    for _, node := range unvisited {
        if minNode == "" || shortestDistances[minNode] > shortestDistances[node] {
            minNode = node
        }
    }

    for node, value := range graph[minNode] {
        if value+shortestDistances[minNode] < shortestDistances[node] {
            shortestDistances[node] = value + shortestDistances[minNode]
            pathNodes[node] = minNode
        }
    }
    unvisited = remove(unvisited, minNode)
    node := destination
    route := []string{}
    for node != source {
        if _, ok := pathNodes[node]; ok {
            route = append([]string{node}, route...)
            node = pathNodes[node]
        } else {
            fmt.Println("Path not reachable")
            break
        }
    }
    route = append([]string{source}, route...)
}
```

True or False

Time Complexity

Before diving into this subsection, time for a quick question!

Time complexity helps us understand the time it takes for the computer to execute a certain algorithm.

Time Complexity

Dijkstra's algorithm takes significant computational time. The time complexity in a general case is O(V²), where V is the number of vertices. This is improved to O(E log V) (where E is the number of edges) if the graph representation is changed to adjacency lists. While a polynomial time complexity such as O(V²) would seem high, it is better than brute force algorithms which provide much higher computational times.

You can find the full working implementation here:

```py
#!/usr/bin/python
# -*- coding: utf-8 -*-
import math

graph = {
    'a': {'b': 5, 'c': 2},
    'b': {'a': 5, 'c': 7, 'd': 8},
    'c': {
        'a': 2,
        'b': 7,
        'd': 4,
        'e': 8,
        },
    'd': {
        'b': 8,
        'c': 4,
        'e': 6,
        'f': 4,
        },
    'e': {'c': 8, 'd': 6, 'f': 3},
    'f': {'e': 3, 'd': 4},
    }

source = 'a'
destination = 'f'

unvisited = graph
shortest_distances = {}
route = []
path_nodes = {}

for nodes in unvisited:
    shortest_distances[nodes] = math.inf
shortest_distances[source] = 0

while unvisited:
    min_node = None
    for current_node in unvisited:
        if min_node is None:
            min_node = current_node
        elif shortest_distances[min_node] \
            > shortest_distances[current_node]:
            min_node = current_node
    for (node, value) in unvisited[min_node].items():
        if value + shortest_distances[min_node] \
            < shortest_distances[node]:
            shortest_distances[node] = value \
                + shortest_distances[min_node]
            path_nodes[node] = min_node
    unvisited.pop(min_node)
node = destination

while node != source:
    try:
        route.insert(0, node)
        node = path_nodes[node]
    except Exception:
        print('Path not reachable')
        break
route.insert(0, source)

if shortest_distances[destination] != math.inf:
    print('Shortest distance is ' + str(shortest_distances[destination]))
    print('And the path is ' + str(route))
```
```js
const graph = {
  a: { b: 5, c: 2 },
  b: { a: 5, c: 7, d: 8 },
  c: { a: 2, b: 7, d: 4, e: 8 },
  d: { b: 8, c: 4, e: 6, f: 4 },
  e: { c: 8, d: 6, f: 3 },
  f: { e: 3, d: 4 },
};

const printTable = (table) => {
  return Object.keys(table)
    .map((vertex) => {
      var { vertex: from, cost } = table[vertex];
      return `${vertex}: ${cost} via ${from}`;
    })
    .join("\n");
};

const tracePath = (table, start, end) => {
  var path = [];
  var next = end;
  while (true) {
    path.unshift(next);
    if (next === start) {
      break;
    }
    next = table[next].vertex;
  }

  return path;
};

const formatGraph = (g) => {
  const tmp = {};
  Object.keys(g).forEach((k) => {
    const obj = g[k];
    const arr = [];
    Object.keys(obj).forEach((v) => arr.push({ vertex: v, cost: obj[v] }));
    tmp[k] = arr;
  });
  return tmp;
};

const dijkstra = (graph, start, end) => {
  var map = formatGraph(graph);

  var visited = [];
  var unvisited = [start];
  var shortestDistances = { [start]: { vertex: start, cost: 0 } };

  var vertex;
  while ((vertex = unvisited.shift())) {
    // Explore unvisited neighbors
    var neighbors = map[vertex].filter((n) => !visited.includes(n.vertex));

    // Add neighbors to the unvisited list
    unvisited.push(...neighbors.map((n) => n.vertex));

    var costToVertex = shortestDistances[vertex].cost;

    for (let { vertex: to, cost } of neighbors) {
      var currCostToNeighbor =
        shortestDistances[to] && shortestDistances[to].cost;
      var newCostToNeighbor = costToVertex + cost;
      if (
        currCostToNeighbor == undefined ||
        newCostToNeighbor < currCostToNeighbor
      ) {
        // Update the table
        shortestDistances[to] = { vertex, cost: newCostToNeighbor };
      }
    }

    visited.push(vertex);
  }

  console.log("Table of costs:");
  console.log(printTable(shortestDistances));

  const path = tracePath(shortestDistances, start, end);

  console.log(
    "Shortest path is: ",
    path.join(" -> "),
    " with weight ",
    shortestDistances[end].cost
  );
};

dijkstra(graph, "a", "f");
```
```java
import java.util.*;

public class Main {

    public static void main(String[] args) {

        HashMap<String, HashMap<String, Integer>> graph = new HashMap<>();
        graph.put("a", new HashMap<>()); graph.get("a").put("b", 5); graph.get("a").put("c", 2);
        graph.put("b", new HashMap<>()); graph.get("b").put("a", 5); graph.get("b").put("c", 7); graph.get("b").put("d", 8);
        graph.put("c", new HashMap<>()); graph.get("c").put("a", 2); graph.get("c").put("b", 7); graph.get("c").put("d", 4); graph.get("c").put("e", 8);
        graph.put("d", new HashMap<>()); graph.get("d").put("b", 8); graph.get("d").put("c", 4); graph.get("d").put("e", 6); graph.get("d").put("f", 4);
        graph.put("e", new HashMap<>()); graph.get("e").put("c", 8); graph.get("e").put("d", 6); graph.get("e").put("f", 3);
        graph.put("f", new HashMap<>()); graph.get("f").put("d", 4); graph.get("f").put("e", 3);

        String sourceNode = "a";
        String destinationNode = "f";

        HashMap<String, Integer> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(sourceNode, 0);
        
        HashMap<String, String> previousNodes = new HashMap<>();

        while (!graph.isEmpty()) {
            String closestNode = findClosestNode(distances);
            int distanceToNode = distances.get(closestNode);
            HashMap<String, Integer> edges = graph.get(closestNode);
            
            for (String adjacentNode : edges.keySet()) {
                int distanceToAdjacent = distanceToNode + edges.get(adjacentNode);
                if (!distances.containsKey(adjacentNode) || distanceToAdjacent < distances.get(adjacentNode)) {
                    distances.put(adjacentNode, distanceToAdjacent);
                    previousNodes.put(adjacentNode, closestNode);
                }
            }
            graph.remove(closestNode);
        }

        List<String> shortestPath = new ArrayList<>();
        String currentNode = destinationNode;
        while (currentNode != null) {
            shortestPath.add(currentNode);
            currentNode = previousNodes.get(currentNode);
        }
        Collections.reverse(shortestPath);

        System.out.println("Shortest distance is " + distances.get(destinationNode));
        System.out.println("And the path is " + shortestPath);
    }

    private static String findClosestNode(HashMap<String, Integer> distances) {
        String closestNode = null;
        for (String node : distances.keySet()) {
            if (closestNode == null || distances.get(node) < distances.get(closestNode)) {
                closestNode = node;
            }
        }
        return closestNode;
    }

}
```
```cpp
#include <iostream>
#include <map>
#include <queue>
#include <limits>
#include <list>
#include <algorithm>

typedef std::map<char, std::map<char, int>> Graph;

Graph createGraph(){
    Graph graph;
    graph['a']['b']=5; graph['a']['c']=2;
    graph['b']['a']=5; graph['b']['c']=7; graph['b']['d']=8;
    graph['c']['a']=2; graph['c']['b']=7; graph['c']['d']=4; graph['c']['e']=8;
    graph['d']['b']=8; graph['d']['c']=4; graph['d']['e']=6; graph['d']['f']=4;
    graph['e']['c']=8; graph['e']['d']=6; graph['e']['f']=3;
    graph['f']['e']=3; graph['f']['d']=4;
    return graph;
}

std::pair<std::vector<char>,int> dijkstra(Graph &graph, char source, char destination){
    std::priority_queue<std::pair<int, char>, std::vector<std::pair<int, char>>, std::greater<std::pair<int, char>>> pq;
    std::map<char, int> dist;
    std::map<char, char> prev;
    for(auto const &pair: graph){
        char node = pair.first;
        dist[node] = std::numeric_limits<int>::max(); prev[node] = -1;
    }
    dist[source] = 0;
    pq.push(std::make_pair(0, source));
    while(!pq.empty()){
        char node = pq.top().second;
        pq.pop();
        for(auto const &pair: graph[node]){
            char adjNode = pair.first;
            int edgeWeight = pair.second;
            if(dist[adjNode] > dist[node] + edgeWeight){
                dist[adjNode] = dist[node] + edgeWeight;
                pq.push(std::make_pair(dist[adjNode], adjNode));
                prev[adjNode] = node;
            }
        }
    }
    std::vector<char> shortestPath;
    char currentNode = destination;
    while(currentNode != source){
        shortestPath.push_back(currentNode);
        currentNode = prev[currentNode];
    }
    shortestPath.push_back(source);
    std::reverse(shortestPath.begin(), shortestPath.end());
    return std::make_pair(shortestPath, dist[destination]);
}

int main(){
    Graph graph = createGraph();
    char sourceNode = 'a';
    char destinationNode = 'f';
    std::pair<std::vector<char>,int> result = dijkstra(graph, sourceNode, destinationNode);
    std::cout<<"Shortest path is "<<result.second<<" and the path is ";
    for(auto const &node: result.first){
        std::cout<<node<<" ";
    }
    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

public class Program{
    static Dictionary<char, Dictionary<char, int>> graph = new Dictionary<char, Dictionary<char, int>>();
    public static void Main(){
        graph['a'] = new Dictionary<char, int>(){ {'b', 5}, {'c', 2} };
        graph['b'] = new Dictionary<char, int>(){ {'a', 5}, {'c', 7}, {'d', 8} };
        graph['c'] = new Dictionary<char, int>(){ {'a', 2}, {'b', 7}, {'d', 4}, {'e', 8} };
        graph['d'] = new Dictionary<char, int>(){ {'b', 8}, {'c', 4}, {'e', 6}, {'f', 4} };
        graph['e'] = new Dictionary<char, int>(){ {'c', 8}, {'d', 6}, {'f', 3} };
        graph['f'] = new Dictionary<char, int>(){ {'e', 3}, {'d', 4} };

        char source = 'a';
        char destination = 'f';
        var result = Dijkstra(graph, source, destination);

        Console.WriteLine("Shortest path is " + result.result + " and the path is " + String.Join("->", result.path));
    }

    static (List<char> path, int result) Dijkstra(Dictionary<char, Dictionary<char, int>> graph, char source, char destination){
        Dictionary<char, int> distances = new Dictionary<char, int>();
        Dictionary<char, char> previousNodes = new Dictionary<char, char>();

        foreach(var node in graph.Keys){
            distances[node] = int.MaxValue;
            previousNodes[node] = default(char);
        }
        distances[source] = 0;

        while(graph.Count > 0){
            char nodeWithMinimalDistance = GetNodeWithMinimalDistance(distances);
            Dictionary<char, int> links = graph[nodeWithMinimalDistance];
            foreach(char linkedNode in links.Keys){
                int possiblyNewDistance = distances[nodeWithMinimalDistance] + links[linkedNode];
                if(possiblyNewDistance < distances[linkedNode]){
                    distances[linkedNode] = possiblyNewDistance;
                    previousNodes[linkedNode] = nodeWithMinimalDistance;
                }
            }

            graph.Remove(nodeWithMinimalDistance);
        }

        List<char> path = new List<char>();
        char folder = destination;

        while(folder != source){
            path.Add(folder);
            folder = previousNodes[folder];
        }

        path.Add(source);
        path.Reverse();

        return (path, distances[destination]);
    }

    static char GetNodeWithMinimalDistance(Dictionary<char, int> distances){
        int minimalDistance = int.MaxValue;
        char nodeWithMinimalDistance = default(char);

        foreach(var node in distances){
            if(node.Value <= minimalDistance){
                minimalDistance = node.Value;
                nodeWithMinimalDistance = node.Key;
            }
        }

        return nodeWithMinimalDistance;
    }
}
``` 
```go
package main
import "fmt"
import "container/heap"
type Graph map[string]map[string]int
type NodeDist struct {
	node string
	dist int
}
type PriorityQueue []*NodeDist
func (prq PriorityQueue) Len() int {
	return len(prq)
}
func (prq PriorityQueue) Less(i, j int) bool {
	return prq[i].dist < prq[j].dist
}
func (prq PriorityQueue) Swap(i, j int) {
	prq[i], prq[j] = prq[j], prq[i]
}
func (prq *PriorityQueue) Push(item interface{}) {
	*prq = append(*prq, item.(*NodeDist))
}
func (prq *PriorityQueue) Pop() interface{} {
	old := *prq
	n := len(old)
	item := old[n-1]
	*prq = old[0 : n-1]
	return item
}
func NewNodeDist(node string) *NodeDist {
	return &NodeDist{
		node: node,
		dist: 1000000,
	}
}
func createGraph() Graph {
	return Graph{
		"a": {"b": 5, "c": 2},
		"b": {"a": 5, "c": 7, "d": 8},
		"c": {"a": 2, "b": 7, "d": 4, "e": 8},
		"d": {"b": 8, "c": 4, "e": 6, "f": 4},
		"e": {"c": 8, "d": 6, "f": 3},
		"f": {"e": 3, "d": 4},
	}
}
func dijkstra(graph Graph, source string, destination string) {
	myHeap := make(PriorityQueue, len(graph))
	i := 0
	distNodes := map[string]*NodeDist{}
	for node := range graph {
		distNodes[node] = NewNodeDist(node)
		myHeap[i] = distNodes[node]
		i++
	}
	distNodes[source].dist = 0
	heap.Init(&myHeap)
	for myHeap.Len() > 0 {
		visitedNode := heap.Pop(&myHeap).(*NodeDist).node
		if visitedNode == destination {
			fmt.Println("Shortest path is ", distNodes[destination].dist)
			fmt.Print("Path is ")
			node := destination
			for node != source {
				fmt.Print(node + " ")
				node = distNodes[node].node
			}
			fmt.Println(source)
			return
		}
		for neighbor, edgeWeight := range graph[visitedNode] {
			newDist := distNodes[visitedNode].dist + edgeWeight
				if newDist < distNodes[neighbor].dist {
					distNodes[neighbor].dist = newDist
					distNodes[neighbor].node = visitedNode
					heap.Fix(&myHeap, myHeap.Index(distNodes[neighbor]))
				}
		}
		delete(graph, visitedNode)
	}
	fmt.Println("No path found from source to destination.")
}
func main() {
	graph := createGraph()
	dijkstra(graph, "a", "f")
}
```

Summary

Dijkstra's algorithm is fundamental in understanding shortest path problems. The implementation of the algorithm may seem daunting at first, but it becomes easier once you understand the basic concept. In the next part of this tutorial, we will explore more shortest path algorithms, and compare them with Dijkstra's algorithm to note the key differences between them.

One Pager Cheat Sheet

The lesson covers Dijkstra's algorithm and its application in solving shortest path problems, including its implementation in Python and comparison to other methods like Breadth-First Search (BFS), A* search algorithm, and Floyd-Warshall algorithm.
The shortest path problems are represented using a graph, requiring a solid understanding of graph concepts.
The graph in mathematics and computer science comprises two key components: vertices or nodes which represent points of connection, and edges which represent the connection between these points, and it can be directed or undirected; any missing options in the multiple choice test notwithstanding, the accurate answer must include both vertices (nodes) and edges.
In shortest path problems, nodes represent cities and edges represent connectivity, with paths determined from one or more source nodes, using either directed or undirected graphs.
In computer science, a graph is a collection of nodes and edges, with directed graphs featuring unidirectional edges, resembling one-way streets, while undirected graphs feature bidirectional edges, similar to two-way streets, with unidirectional and bidirectional describing the nature of node connectivity in these graphs.
The problem representation requires the input graph to have one source node and non-negative weights for Dijkstra's algorithm, which finds the distance values for the shortest path from the source node to each unvisited node n, aiding in determining the shortest path between complex nodes, such as hundreds of cities.
The Dijkstra's algorithm is implemented by initializing variables such as a list of unvisited nodes, a list of distances to nodes (with all initially set to infinity except the source node set to 0), and a list of visited nodes that form the shortest path; the algorithm, beginning with a source node, adjusts distances of nodes in this context.
The algorithm progresses by moving to the unvisited node with smallest distance, node C, and updating the distances of nodes D and E to 6 and 10 respectively, after finding that the sum of the source-to-node distances for these nodes is greater than the original distance.
The unvisited node with the smallest distance value, B, is moved to the visited node list, but as visiting B creates no new paths, no distance values are altered and B is not added to the path.
The unvisited node with the smallest distance value, node D, is visited to discover a new connection F, which has its distance value updated to 10 as this provides the shortest path from the previous node C.
The algorithm proceeds in lexicographic order, visiting node E first, which does not alter the shortest path or the distance values of the other nodes.
The shortest path to destination node F is completed by adding the path from node D to F, resulting in a total weight of 10, which is smaller than any other path to F.
Dijkstra's algorithm can accurately calculate the shortest path in both directed and undirected graphs, by considering the least cumulative weight from the start node and treating edges in undirected graphs as two separate directed edges.
Dijkstra's algorithm doesn't depend on the direction of edges and can represent the graph as an adjacency list using nested dictionaries.
- An adjacency list stores each node's reachable neighbors plus the cost to get there.
- An adjacency list stores each node's neighbors and the cost to reach them.
The unvisited, path, and distance lists of nodes are initialized, setting the initial distance values of all nodes to infinity except the source node which is set to zero.
- Dijkstra begins with source distance 0, all other distances ∞, and no finalized nodes.
- Initialize source distance to 0; all other shortest distances start as ∞.
The algorithm selects the unvisited node with the shortest distance from the source, updates distances by checking all the neighboring nodes, adds nodes to the path list when distance is updated, and repeats this process until every node in the graph is visited.
- Relaxation updates a neighbor only when current distance + edge weight beats its known distance.
- Relaxation updates a neighbor when the route through the current node is cheaper.
To find the shortest path between nodes, the reachability of the destination node from the source node is checked, after which the destination is added to the route list if reachable.
Time complexity is an important tool that helps us estimate the efficiency of an algorithm, identify bottlenecks in the code, calculate the time taken to execute its steps, measure the speed of a process, and determine the optimal solution.
Dijkstra's algorithm has a O(E log V) time complexity using adjacency lists, which is better than brute force algorithms.
Dijkstra's algorithm is a fundamental concept for understanding shortest path problems, and will be compared to other algorithms in the next part of the tutorial.

Open interactive view →