Dijkstras_Shortest_Path_Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_qq1t7ap"
   },
   "source": [
    "## Dijkstra's Shortest Path Algorithm\n",
    "Suppose there is graph having nodes, where each node represents a city. A few pair of nodes are connected to each other, with their distance mentioned on the conneting edge, as shown in the figure below:\n",
    "<img style=\"float: center;height:250px;\" src=\"graph1.png\"><br>\n",
    "\n",
    "To find the shortest path from a given source to destination node in the example above, a Greedy approach would be - *At each current node, keep track of the nearest neighbour. We can determine the path in the reverse order once we have a table of nearest neighbours (optimal previous nodes).* For example, C is the optimal previous node for E. This way, the shortest path from `A` to `E` would be `A --> D --> C --> E`, as shown below:\n",
    "<img style=\"float: center;height:250px;\" src=\"graph2.png\"><br>\n",
    "\n",
    "And, if we wish to print the distance of each node from `A`, then it would look like:\n",
    "<img style=\"float: center;height:250px;\" src=\"graph3.png\"><br>\n",
    "\n",
    "Here, the **Previous Optimal Node** is the \"best\" node which could lead us to the current node. \n",
    "\n",
    "## The Problem\n",
    "Using Dijkstra's algorithm, find the shortest path to all the nodes starting from a given single source node.  You need to print the distance of each node from the given source node. For the example quoted above, the distance of each node from `A` would be printed as:<br>\n",
    "```\n",
    "{'A': 0, 'D': 2, 'B': 5, 'E': 4, 'C': 3, 'F': 6}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_75htzek"
   },
   "source": [
    "## The Algorithm\n",
    "1. Create a `result` dictionary. At the end of the program, `result` will have the shortest distance (value) for all nodes (key) in the graph. For our example, it will become as `{'A': 0, 'B': 5, 'C': 3, 'D': 2, 'F': 6, 'E': 4}`<br><br>\n",
    "1. Start with the source node. Distance from source to source itself is 0.  <br><br>\n",
    "1. The distance to all other nodes from the source is unknown initially, therefore set the initial distance to infinity.  <br><br>\n",
    "1. Create a set `unvisited` containing nodes that have not been visited. Initially, it will have all nodes of the graph.<br><br>\n",
    "1. Create a `path` dictionary that keeps track of the previous node (value) that can lead to the current node (key). At the end of the program, for our example, it will become as `{'B': 'A', 'C': 'D', 'D': 'A', 'F': 'C', 'E': 'C'}`. <br><br>\n",
    "1. As long as `unvisited` is non-empty, repeat the following:\n",
    " - Find the unvisited node having smallest known distance from the source node.  <br><br>\n",
    " - For the current node, find all the **unvisited neighbours**. For this, you have calculate the distance of each unvisited neighbour.  <br><br>\n",
    " - If the calculated distance of the **unvisited neighbour** is less than the already known distance in `result` dictionary, update the shortest distance in the `result` dictionary. <br><br>\n",
    " - If there is an update in the `result` dictionary, you need to update the `path` dictionary as well for the same key. <br><br>\n",
    " - Remove the current node from the `unvisited` set.\n",
    "\n",
    "\n",
    "**Note** - This implementation of the Dijkstra's algorithm is not very efficient. Currently it has a *O(n^2)* time complexity. We will see a better version in the next lesson - \"Graph Algorithms\" with *O(nlogn)* time complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "graffitiCellId": "id_kowh9ph"
   },
   "outputs": [],
   "source": [
    "# Helper Code\n",
    "from collections import defaultdict\n",
    "import sys\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.nodes = set()                   # A set cannot contain duplicate nodes\n",
    "        self.neighbours = defaultdict(list)  # Defaultdict is a child class of Dictionary that provides a default value for a key that does not exists.\n",
    "        self.distances = {}                  # Dictionary. An example record as ('A', 'B'): 6 shows the distance between 'A' to 'B' is 6 units\n",
    "\n",
    "    def add_node(self, value):\n",
    "        self.nodes.add(value)\n",
    "\n",
    "    def add_edge(self, from_node, to_node, distance):\n",
    "        self.neighbours[from_node].append(to_node)\n",
    "        self.neighbours[to_node].append(from_node)\n",
    "        self.distances[(from_node, to_node)] = distance\n",
    "        self.distances[(to_node, from_node)] = distance    # lets make the graph undirected / bidirectional \n",
    "        \n",
    "    def print_graph(self):\n",
    "        print(\"Set of Nodes are: \", self.nodes)\n",
    "        print(\"Neighbours are: \", self.neighbours)\n",
    "        print(\"Distances are: \", self.distances)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_cgrnklc"
   },
   "source": [
    "### Exercise - Write the function definition here\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "graffitiCellId": "id_lo3by3j"
   },
   "outputs": [],
   "source": [
    "''' TO DO: Find the shortest path from the source node to every other node in the given graph '''\n",
    "def dijkstra(graph, source):\n",
    "    result = {node: sys.maxsize for node in graph.nodes}  # Start with all distances as infinity\n",
    "    result[source] = 0  # Distance from source to itself is 0\n",
    "    unvisited = set(graph.nodes)  # All nodes are unvisited initially\n",
    "    path = {node: None for node in graph.nodes}  # Tracks the best previous node\n",
    "\n",
    "    # Step 2: Loop until all nodes have been visited\n",
    "    while unvisited:\n",
    "        # Find the unvisited node with the smallest known distance\n",
    "        current_node = find_min_node(unvisited, result)\n",
    "        \n",
    "        # If current_node is still infinity, we break the loop as remaining nodes are disconnected\n",
    "        if result[current_node] == sys.maxsize:\n",
    "            break\n",
    "        \n",
    "        # Step 3: Explore the neighbors of the current node\n",
    "        for neighbour in graph.neighbours[current_node]:\n",
    "            if neighbour in unvisited:  # Only consider unvisited neighbours\n",
    "                # Calculate the new tentative distance to this neighbor\n",
    "                new_distance = result[current_node] + graph.distances[(current_node, neighbour)]\n",
    "                \n",
    "                # If a shorter path is found, update the distance and path\n",
    "                if new_distance < result[neighbour]:\n",
    "                    result[neighbour] = new_distance\n",
    "                    path[neighbour] = current_node  # Update the optimal path\n",
    "\n",
    "        # Step 5: Remove the current node from the unvisited set\n",
    "        unvisited.remove(current_node)\n",
    "        # 1. Find the unvisited node having smallest known distance from the source node.\n",
    "        \n",
    "        # 2. For the current node, find all the unvisited neighbours. For this, you have calculate the distance of each unvisited neighbour.\n",
    "        \n",
    "        # 3. If the calculated distance of the unvisited neighbour is less than the already known distance in result dictionary, update the shortest distance in the result dictionary.        \n",
    "\n",
    "        # 4. If there is an update in the result dictionary, you need to update the path dictionary as well for the same key.\n",
    "                    \n",
    "        # 5. Remove the current node from the unvisited set.\n",
    "\n",
    "    return result\n",
    "    \n",
    "def find_min_node(unvisited, result):\n",
    "    min_distance = float('inf')  # Start with an infinite distance\n",
    "    min_node = None\n",
    "    \n",
    "    for node in unvisited:\n",
    "        # We are looking for the node with the smallest distance in result.\n",
    "        if result[node] < min_distance:\n",
    "            min_distance = result[node]\n",
    "            min_node = node\n",
    "    \n",
    "    return min_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_hae4wv9"
   },
   "source": [
    "### Test - Let's test your function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "graffitiCellId": "id_gh91otb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': 0, 'D': 2, 'C': 4, 'B': 3, 'E': 3}\n"
     ]
    }
   ],
   "source": [
    "# Test 1\n",
    "testGraph = Graph()\n",
    "for node in ['A', 'B', 'C', 'D', 'E']:\n",
    "    testGraph.add_node(node)\n",
    "\n",
    "testGraph.add_edge('A','B',3)\n",
    "testGraph.add_edge('A','D',2)\n",
    "testGraph.add_edge('B','D',4)\n",
    "testGraph.add_edge('B','E',6)\n",
    "testGraph.add_edge('B','C',1)\n",
    "testGraph.add_edge('C','E',2)\n",
    "testGraph.add_edge('E','D',1)\n",
    "\n",
    "print(dijkstra(testGraph, 'A'))     # {'A': 0, 'D': 2, 'B': 3, 'E': 3, 'C': 4}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "graffitiCellId": "id_i5pengy"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'C': 10, 'A': 0, 'B': 5}\n"
     ]
    }
   ],
   "source": [
    "# Test 2\n",
    "graph = Graph()\n",
    "for node in ['A', 'B', 'C']:\n",
    "    graph.add_node(node)\n",
    "    \n",
    "graph.add_edge('A', 'B', 5)\n",
    "graph.add_edge('B', 'C', 5)\n",
    "graph.add_edge('A', 'C', 10)\n",
    "\n",
    "print(dijkstra(graph, 'A'))        # {'A': 0, 'C': 10, 'B': 5}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "graffitiCellId": "id_mna3duu"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'A': 0, 'F': 6, 'D': 2, 'C': 3, 'B': 5, 'E': 4}\n"
     ]
    }
   ],
   "source": [
    "# Test 3\n",
    "graph = Graph()\n",
    "for node in ['A', 'B', 'C', 'D', 'E', 'F']:\n",
    "    graph.add_node(node)\n",
    "    \n",
    "graph.add_edge('A', 'B', 5)\n",
    "graph.add_edge('A', 'C', 4)\n",
    "graph.add_edge('D', 'C', 1)\n",
    "graph.add_edge('B', 'C', 2)\n",
    "graph.add_edge('A', 'D', 2)\n",
    "graph.add_edge('B', 'F', 2)\n",
    "graph.add_edge('C', 'F', 3)\n",
    "graph.add_edge('E', 'F', 2)\n",
    "graph.add_edge('C', 'E', 1)\n",
    "\n",
    "print(dijkstra(graph, 'A'))       # {'A': 0, 'C': 3, 'B': 5, 'E': 4, 'D': 2, 'F': 6}"
   ]
  }
 ],
 "metadata": {
  "graffiti": {
   "firstAuthorId": "af9e0b36-2ad2-11ea-83c4-a78dc7ef519f",
   "id": "id_muf5xfw",
   "language": "EN"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}