{ "cells": [ { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "# Code adapted from:\n", "# https://www.geeksforgeeks.org/python-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/\n", "class Graph():\n", " \n", " # Initializes empty adjacency matrix of specified size\n", " def __init__(self, vertices):\n", " self.V = vertices\n", " self.graph = [[0 for column in range(vertices)]\n", " for row in range(vertices)]\n", " \n", " def printSolution(self, dist, pred):\n", " print(\"Vertex, Distance, Predecessor\")\n", " for node in range(self.V):\n", " print(node, dist[node], pred[node])\n", " \n", " # Find vertex with minimum distance value from the ones we have visited\n", " def minDistance(self, dist, sptSet):\n", " min = 9999\n", " for v in range(self.V):\n", " if dist[v] < min and sptSet[v] == False:\n", " min = dist[v]\n", " min_index = v\n", " return min_index\n", " \n", " # Funtion that implements Dijkstra's single source\n", " # shortest path algorithm for a graph represented\n", " # using adjacency matrix representation\n", " def dijkstra(self, src):\n", " \n", " dist = [9999] * self.V\n", " dist[src] = 0\n", " sptSet = [False] * self.V\n", " \n", " pred = [9999] * self.V\n", " pred[src] = src\n", "\n", " \n", " # For better running time, replace this with priority queue check\n", " for foo in range(self.V): # We need this many iterations\n", " # Pick closest vertex we haven't visited yet\n", " u = self.minDistance(dist, sptSet)\n", " sptSet[u] = True # Add it to set for tree\n", " \n", " # See if there is a shorter path to anywhere through this node\n", " for v in range(self.V):\n", " # If there is an edge from u to v\n", " # and we have not visited v yet\n", " # and u provides a new shorter path to v\n", " if self.graph[u][v] > 0 and \\\n", " sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:\n", " # Update shortest known distance\n", " dist[v] = dist[u] + self.graph[u][v]\n", " pred[v] = u\n", " \n", " self.printSolution(dist, pred)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "g = Graph(6)\n", "g.graph = [[0, 7, 9, 0, 0, 14],\n", " [7, 0, 10, 15, 0, 0],\n", " [9, 10, 0, 11, 0, 2],\n", " [0, 15, 11, 0, 6, 2],\n", " [0, 0, 0, 6, 0, 9],\n", " [14, 0, 2, 0, 9, 0]\n", " ]" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "g = Graph(9)\n", "g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],\n", " [4, 0, 8, 0, 0, 0, 0, 11, 0],\n", " [0, 8, 0, 7, 0, 4, 0, 0, 2],\n", " [0, 0, 7, 0, 9, 14, 0, 0, 0],\n", " [0, 0, 0, 9, 0, 10, 0, 0, 0],\n", " [0, 0, 4, 14, 10, 0, 2, 0, 0],\n", " [0, 0, 0, 0, 0, 2, 0, 1, 6],\n", " [8, 11, 0, 0, 0, 0, 1, 0, 7],\n", " [0, 0, 2, 0, 0, 0, 6, 7, 0]\n", " ]\n" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "from graphviz import Digraph\n", "dot = Digraph()\n", "def showgraph(adj,v): \n", " for i in range(0,v):\n", " dot.node(str(i))\n", " for i in range(v):\n", " for conn in range(v):\n", " if adj[i][conn] > 0:\n", " dot.edge(str(i), str(conn))\n", " " ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "%3\n", "\n", "\n", "\n", "0\n", "\n", "0\n", "\n", "\n", "\n", "1\n", "\n", "1\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "\n", "\n", "\n", "5\n", "\n", "5\n", "\n", "\n", "\n", "0->5\n", "\n", "\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "\n", "\n", "\n", "3\n", "\n", "3\n", "\n", "\n", "\n", "1->3\n", "\n", "\n", "\n", "\n", "\n", "2->0\n", "\n", "\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "2->5\n", "\n", "\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "\n", "\n", "\n", "3->2\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "4\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "\n", "\n", "\n", "3->5\n", "\n", "\n", "\n", "\n", "\n", "4->3\n", "\n", "\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "5->0\n", "\n", "\n", "\n", "\n", "\n", "5->2\n", "\n", "\n", "\n", "\n", "\n", "5->4\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "showgraph(g.graph, g.V)\n", "dot" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Vertex, Distance, Predecessor\n", "0 0 0\n", "1 7 0\n", "2 9 0\n", "3 20 2\n", "4 20 5\n", "5 11 2\n" ] } ], "source": [ "g.dijkstra(0)" ] } ], "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 }