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 Date Difference In Days Python 01-04-2023
Bellman Ford Algorithm In Python Python 25-03-2023
Python Program To Display Current Date And Time Python 24-03-2023
Binary Search Tree Implementation Python Python 21-03-2023
Python Program To Check Palindrome Number Python 12-03-2023
How to Merge Two PDF Files Using Python Python 12-03-2023
Python Tuples Example Python 19-11-2021
Python Iterator Example Python 12-11-2021
Python Lambda Functions Python 11-11-2021
Integer To String In Python Python 22-10-2021
Python Datetime Format Python 21-10-2021
Range Function In Python | Python range () Python 11-10-2021
Python Desktop Notification Popup In Linux Python 10-07-2021
Python JSON Parser Example | How To Parse JSON In Python Python 25-06-2021
Python PIP | How To Install Packages In Python Python 16-06-2021
How To Access Python Dictionary Python 14-06-2021
Dictionary In Python Examples Python 10-06-2021
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

1 2