Dijkstra’s-Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We will create a program that finds the shortest path through a graph using its edges using Dijkstra's algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortest_path(graph,links_weight):  # function to find shortest distance between starting node and remaining nodes of a graph\n",
    "    \n",
    "    distance_node={v: float('inf') for v in list(graph)} # distance dictionary initially all nodes have infinity distance\n",
    "    start_node=list(graph)[0]        # Our starting node\n",
    "    distance_node[1]=0               # distance of our starting node is zero\n",
    "    distance=float('inf')            # distance variable whose current value is infinity\n",
    "    visited_node=[]                  # list of visited nodes, initially empty\n",
    "    unvisited_node=[v for v in list(graph)]   # list of unvisited nodes, initially has all the nodes as we haven't visited any \n",
    "    while len(unvisited_node)!=0:    # loop runs till unvisited nodes list becomes empty\n",
    "        \n",
    "        for u in graph[start_node]: # Connecting nodes to starting node\n",
    "            if distance_node[start_node]+links_weight[(start_node,u)] < distance_node[u]: # change distance of connected nodes if initial distance is greater than current distance\n",
    "                distance_node[u]=distance_node[start_node]+links_weight[(start_node,u)]\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "                \n",
    "        visited_node.append(start_node)  # append current node to visited nodes list  \n",
    "        unvisited_node.remove(start_node)  # remove current node from unvisited nodes list\n",
    "        \n",
    "        \n",
    "        for w in unvisited_node:         # node in unvisited nodes list which has minimum distance from starting node will be visited next\n",
    "            if distance_node[w]<distance:\n",
    "                distance=distance_node[w]\n",
    "                new_node=w\n",
    "            else:\n",
    "                continue\n",
    "                \n",
    "        start_node=w\n",
    "        \n",
    "    \n",
    "    return distance_node  # returning dictionary of nodes with values of distances from the starting node\n",
    "                    \n",
    "    \n",
    "            \n",
    "    \n",
    "                \n",
    "              \n",
    "                \n",
    "                \n",
    "                \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{4: 9, 2: 12, 3: 8, 5: 20, 6: 15}\n",
      "The shortest distance of node 4 from node 1 is: 9 \n",
      "The shortest distance of node 2 from node 1 is: 12 \n",
      "The shortest distance of node 3 from node 1 is: 8 \n",
      "The shortest distance of node 5 from node 1 is: 20 \n",
      "The shortest distance of node 6 from node 1 is: 15 \n"
     ]
    }
   ],
   "source": [
    "graph={1:[4,2,3],4:[1,3],2:[1,3,6],3:[4,1,2,5,6],5:[3],6:[2,3]} \n",
    "# links with cost\n",
    "l_w={(4,3):1,(3,4):1,(4,1):10,(1,4):10,(1,3):8,(3,1):8,(2,3):4,(3,2):4,(1,2):15,(2,1):15,(3,5):12,(5,3):12,(3,6):7,(6,3):7,(2,6):5,(6,2):5}\n",
    "distance=shortest_path(graph,l_w)\n",
    "g=list(graph)\n",
    "distance.pop(g[0])\n",
    "print(distance)\n",
    "for u in list(distance):\n",
    "    print(f'The shortest distance of node {u} from node {g[0]} is: {distance[u]} ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}