Solution Review: Implementing Dijkstra's
In this lesson, we'll look at a way to implement Dijkstra's Algorithm.
We'll cover the following...
Solution #1: Calculating All Paths
Press + to interact
def Dijkstra(graph, src, dst):number_of_nodes = len(graph[0]) # Number of nodes in the graphparent = [-1] * number_of_nodes # Setting up various listsvisited = []unvisited = [i for i in range(number_of_nodes)]distance = [16] * number_of_nodes # The distance list initially has a distance of infinite for all but the source nodedistance[src] = 0shortest_path = [] # This list will have the shortest path at the endcurrent = src # We start with the sourcewhile(len(unvisited)>0):# Visit all neighbors of current and update distancefor i in range(number_of_nodes):if(graph[current][i]>=0 and distance[i] > graph[current][i]+distance[current]):distance[i] = graph[current][i]+distance[current] # Update distanceparent[i] = current # Set new parentunvisited.remove(current) # Move current node from unvisited to vistedvisited.append(current)if(len(unvisited) != 0):current = unvisited[0] # New current node is an unvisited node with the smallest 'distance'for n in unvisited:if(distance[n] < distance[current]):current = ncurr = dst # Some code to get the shortest path from 'parent'shortest_path.append(curr)cost = 0while curr is not src:if parent[curr] == -1: # If there is no path to the source nodereturn([[],-1])cost = cost + graph[curr][parent[curr]] # The cost is the sum of the links in a pathcurr = parent[curr]shortest_path.append(curr)shortest_path.reverse()return([shortest_path, cost])def main():graph = [[0,1,5,-1,-1],[1,0,3,-1,9],[5,3,0,4,-1],[-1,-1,4,0,2],[-1,9,-1,2,0]]src = 0dst = 3print(Dijkstra(graph,src,dst))if __name__ == "__main__":main()
Explanation
Let’s go through this code line by line.
- Lines 1-9: we set up a few variables that are important for the implementation.
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy