Search⌘ K
AI Features
Home
Courses
Grokking Computer Networking for Software Engineers

Solution Review: Implementing Dijkstra's

Explore the implementation of Dijkstra's algorithm for calculating shortest paths in network routing. Understand how to set up variables, update distances, and construct shortest paths efficiently. Learn two solution approaches including an optimized one that stops when the destination route is found. This lesson helps you grasp network layer routing techniques essential for software engineers.

We'll cover the following...

Solution #1: Calculating All Paths

Python 3.5
def Dijkstra(graph, src, dst):
    number_of_nodes = len(graph[0])   # Number of nodes in the graph
    parent = [-1] * number_of_nodes    # Setting up various lists
    visited = []                    
    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 node
    distance[src] = 0
    shortest_path = []                # This list will have the shortest path at the end
    current = src                     # We start with the source
    while(len(unvisited)>0):   
      # Visit all neighbors of current and update distance
      for 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 distance
          parent[i] = current # Set new parent
      unvisited.remove(current) # Move current node from unvisited to visted
      visited.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 = n
    curr = dst # Some code to get the shortest path from 'parent' 
    shortest_path.append(curr)
    cost = 0
    while curr is not src:
      if parent[curr] == -1: # If there is no path to the source node
        return([[],-1])
      cost = cost + graph[curr][parent[curr]] # The cost is the sum of the links in a path
      curr = 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 = 0
    dst = 3
    print(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.
    1. The number_of_nodes is the number of nodes in the graph. It’s equivalent to the number of rows/columns of the given graph. This variable is not necessary for the algorithm itself, but makes calculating other variables clear and easy.
    2. The parent list will map each node to its ‘parent’ or the previous node in the shortest path to the source node. Initialized to
...