{
"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"
],
"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
}