Answer to Question #305740 in Python for eranna

Question

Given undirected weighted graph, write a program to find shortest paths from designated source vertex all other vertices graph using Dijkstra’s shortest path algorithm. Input Format: input is text file which describes undirected graph. first line file specifies n, m, s, number vertices, number of edges and source vertex respectively. next m lines specify m edges graph, one line per edge. edge is described by its end points followed by weight of that edge. If number of vertices is n, assume that vertices of graph are numbered (0,1,..n-1). Also assume that edge weights are non-negative. Output Format: Print shortest path from source vertex to each vertices in graph, along with length shortest path. Sample Input ( graph shown on right): 5 8 0 0 1 4 0 2 2 1 2 1 1 3 2 1 4 3 2 3 4 2 4 5 3 4 1 Sample Output : Shortest path to 0: 0 ; cost = 0 Shortest path to 1: 0, 2, 1; cost = 3 Shortest path to 2: 0, 2; cost = 2 Shortest path to 3: 0, 2, 1, 3; cost = 5 Shortest path to 4: 0, 2, 1, 4; cost = 6

Answer 1

import sys


class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printSolution(self, dist):
        print("Vertex \tDistance from Source")
        for node in range(self.V):
            print(node, "\t", dist[node])


    def minDistance(self, dist, sptSet):


        min = sys.maxsize


        for u in range(self.V):
            if dist[u] < min and sptSet[u] == False:
                min = dist[u]
                min_index = u

        return min_index


    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):


            x = self.minDistance(dist, sptSet)


            sptSet[x] = True


            for y in range(self.V):
                if self.graph[x][y] > 0 and sptSet[y] == False and \
                        dist[y] > dist[x] + self.graph[x][y]:
                    dist[y] = dist[x] + self.graph[x][y]

        self.printSolution(dist)



g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]
           ];

g.dijkstra(0);