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.
Similar Programs Chapter Last Updated
Python Program To Check Whether Element Present In Set Or Not Example Python 04-10-2023
Python Program To Find Maximum And Minimum Number In A Set Python 04-10-2023
Python Program To Check Symmetric Matrix Python 04-10-2023
Python Program To Find Subsets Of A Set Python 04-10-2023
Python Program To Find Power Set Of A Set Python 04-10-2023
Remove All Duplicates From List Python Python 04-10-2023
Python Program To Find Symmetric Difference Of Two Sets Python 27-09-2023
Python Program To Find Common Item From Two Set Python 27-09-2023
Python Program To Get Unique Values From A List Python 27-09-2023
Python Encode And Decode String With Key Python 24-09-2023
Python Simple Encrypt Decrypt String Python 24-09-2023
Python Format String To Specific Length Python 24-09-2023
Python Code To Check If String Contains Substring Python 24-09-2023
Python Program To Find Most Repeated Word In A String Python 23-09-2023
Split String Into Words Python Python 23-09-2023
Remove All Punctuation Python Python 23-09-2023
Python Program To Reverse An Array Python 23-09-2023
Python Program To Find Number Of Palindrome In A String Python 23-09-2023
Python Program To Find Longest Common Substring Python 23-09-2023
Python Program To Find Number Of Days In A Given Month And Year Python 22-09-2023
Python Program To Calculate Age Of A Person Python 22-09-2023
Python Code To Get Day Of Week Python 22-09-2023
Python Convert String To Date Without Time Python 22-09-2023
Python Program To Print Current Date And Time In Format dd/mm/yyyy Python 22-09-2023
Python Program To Find Working Days In A Month Python 19-09-2023
Python Code To Change Date Format Python 16-09-2023
Python Program To Calculate Number Of Days Between Two Dates Python 16-09-2023
Python Program To Calculate Age In Years Months And Days Python 16-09-2023
Python Program To Schedule A Job To Run After A Certain Amount Of Time Python 10-08-2023
Python Program To Schedule A Job To Run Randomly Once A Day Python 10-08-2023

1 2 3 4