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)