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).
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.
Dijkstra's Algorithm Python code:
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)
