Shortest Path Algorithm In Python

Chapter: Python Last Updated: 23-02-2021 03:13:25 UTC

Program:

            /* ............... START ............... */
                
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph
 
# Library for INT_MAX
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])
 
    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):
 
        # Initilaize minimum distance for next node
        min = sys.maxsize
 
        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v
 
        return min_index
 
    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):
 
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V
 
        for cout in range(self.V):
 
            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)
 
            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True
 
            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and
                   sptSet[v] == False and
                   dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]
 
        self.printSolution(dist)
 
 
# Driver program
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)
                /* ............... END ............... */
        

Output

Vertex tDistance from Source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

Notes:

  • Shortest path algorithms are a family of algorithms designed to solve the shortest path problem.
  • Shortest path algorithms typically operate on some input graph, GG. Graph has some vertices like VV, and edges, EE, that connect them. If the edges have weights, the graph is called a weighted graph.
  • There are also different types of shortest path algorithms. From the graph we have to find the shortest path between point A and B. Please refer the program for clarification.

Tags

Dijkstra’s Algorithm, Shortest path algorithm, Python, DSA

Similar Programs Chapter Last Updated
Merge Sort In Python Python 01-12-2020
Kruskal Algorithm In Python Python 28-11-2020
Python Mysql Connector Example Python 21-11-2020
Add To Set Python Python 05-10-2018
Set In Python Python 05-10-2018
List In Python Python 29-09-2018
Integer To String Python Python 29-09-2018
Python Variables Python 21-09-2018
Python String Contains Python 15-09-2018
String In Python Python 22-09-2018
Python Switch Statement Python 20-09-2018
Python Function Example Python 14-09-2018
Python If Statement Python 14-09-2018
Area Of Triangle In Python Python 14-09-2018
Python Square Root Python 22-09-2018
Add Two Numbers In Python Python 13-09-2018
Python Comments Python 22-09-2018
Python Hello World Python 14-09-2018

1