Discover the Power of Dijkstra's Algorithm: Python Edition.

Shortest paths between nodes use case.

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph. The original algorithm version is used to find the shortest path between two given nodes. The most commonly used variant sets a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, constructing a shortest-path tree (SPT).

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.

The algorithm uses a greedy approach, trying to find the next best solution hoping that the end result is the best solution for the whole problem.

The main steps for Dijkstra's algorithm are:
- Set the ending vertex distance to zero. Assign this vertex as current. - Find all vertices leading to the current vertex and calculate their distances to the end. - Mark the current vertex as visited. - Set the vertex with the smallest distance as current, repeat from step 2.

1. Dijkstra's Algorithm Python code:

2. ``````
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 \t Distance from Source:")
for node in range(self.V):
print(node, "\t\t", dist[node])

# find the vertex with minimum distance value
def minDistance(self, dist, sptSet):

min = 1e7

# Search not nearest vertex
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v

return min_index

def Dijkstra(self, src):

dist = [1e7] * self.V
dist[src] = 0
sptSet = [False] * self.V

for cout in range(self.V):

# Pick the minimum distance vertex
u = self.minDistance(dist, sptSet)

# Put it in the shortest path tree
sptSet[u] = True

# Update dist value of the adjacent vertices
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(7)

g.graph = [[0, 0, 1, 2, 0, 0, 0],
[0, 0, 2, 0, 0, 3, 0],
[1, 2, 0, 1, 3, 0, 0],
[2, 0, 1, 0, 0, 0, 1],
[0, 0, 3, 0, 0, 2, 0],
[0, 3, 0, 0, 2, 0, 1],
[0, 0, 0, 1, 0, 1, 0]]

g.Dijkstra(0)
``````