Question

PYTHON ONLY

Implement the Dijkstra’s Shortest path algorithm in Python. A graph with 10 nodes (Node 0 to node 9) must be implemented. You are supposed to denote the distance of the edges via an adjacency matrix (You can assume the edge weights are either 0 or a positive value). The adjacency matrix is supposed to be a 2-D array and it is to be inputted to the graph. Remember that the adjacency list denotes the edge values for the corresponding nodes. An example driver program for 3 nodes is given below:

myGraph = GraphGen(3, adjMat) source = 0 print

“Showing the Dijskstra result for the node” , source

source.showList(source)

After executing the above program your output should look like:

For Vertex 0, the minimum distance to vertex 0 is 0

For Vertex 1, the minimum distance to vertex 0 is 4

For Vertex 2, the minimum distance to vertex 0 is 2

The python code MUST be able to handle 10 nodes.

Answer 1

# Input :
# 4 4
# 0 1 3
# 0 3 5
# 1 2 1
# 2 3 8

# Output 1 :
# 0 0
# 1 3
# 2 4
# 3 5

import sys

class Graph:

  

def __init__(self,nVertices):

self.nVertices = nVertices

self.adjMatrix = [ [ 0 for i in range(nVertices)] for j in range(nVertices)]

  

def addEdge(self,v1,v2,wt):

self.adjMatrix[v1][v2] = wt

self.adjMatrix[v2][v1] = wt

  

def __getMinVertexD(self,visited,weight):

minVertex = -1

for i in range(self.nVertices):

if(visited[i] is False and (minVertex == -1 or (weight[minVertex] > weight[i]))):

minVertex = i

return minVertex

  

def djikstra(self):

  

visited = [False for i in range(self.nVertices)]

dist = [sys.maxsize for i in range(self.nVertices)]

dist[0] = 0

for i in range(self.nVertices - 1):

minVertex = self.__getMinVertexD(visited,dist)

visited[minVertex] = True

  

for j in range(self.nVertices):

if (self.adjMatrix[minVertex][j] > 0 and visited[j] is False):

if(dist[j] > dist[minVertex] + self.adjMatrix[minVertex][j]):

dist[j] = dist[minVertex] + self.adjMatrix[minVertex][j]
  

for i in range(self.nVertices):

print(str(i) + " " + str(dist[i]))

li = [int(ele) for ele in input().split()]

n = li[0]

E = li[1]

g = Graph(n)

for i in range(E):

curr_edge = [int(ele) for ele in input().split()]

g.addEdge(curr_edge[0],curr_edge[1],curr_edge[2])

g.djikstra()