This code implements Dijkstra's shortest path algorithm to find the...

July 1, 2025 at 05:16 AM

visited = []
dist = []

def dejkstra(source,graph,n):
     for v in range(n):
          visited.append(0)
          dist.append(graph[source][v])

     visited[source] = 1
     dist[source] = 0
     for ecount in range(n):
          min = 999
          for v in range(n):
               if visited[v]==0 and dist[v]<min:
                    min = dist[v]
                    u = v 
          visited[u]=1
          for j in range(n):
               if visited[j] == 0 and dist[u]+graph[u][j] < dist[j]:
                    dist[j] = dist[u]+graph[u][j]

def main():
      graph=[ [0,3,999,7,999],
            [3,0,4,2,999],
            [999,4,0,5,6],
            [7,2,5,0,4],
            [999,999,6,4,0]]
      n = len(graph[0])
      source = int(input("Enter source node"))
      print("Minimum distance from the source node is :")
      dejkstra(source,graph,n)
      for i in range(n):
           print(source,"----->",i,"======",dist[i])

main()

This code implements Dijkstra's shortest path algorithm to find the minimum distance from a given source node to all other nodes in a graph represented as a 2D matrix (a weighted adjacency matrix). Here's a breakdown of what the code does:

Function Details

Global variables:

visited: List that tracks whether a node has already been included in the shortest path computation.
dist: List that stores the estimated shortest distance from the source node to all other nodes.

`dejkstra(source, graph, n)` function:

Initialization:
- It initializes the visited list with 0 for all nodes (indicating no nodes have been visited yet).
- Initializes the dist list with the distance of each node from the source node. Distances are taken from the source row of the graph.
  - If a certain node is unreachable from the source, its distance is initialized as 999 (a placeholder for infinity).
- Marks the source node as visited (1) and sets its distance to 0.
Iterative shortest path finding:
- For every node (ecount loop of size n):
  - Find the unvisited node (u) with the smallest distance (dist[u]).
  - Mark node u as visited.
  - Update the distance of all unvisited neighbors (j) of node u based on: [ \text{dist[j]} = \min(\text{dist[j]}, \text{dist[u]} + \text{graph[u][j]}) ]

`main()` function:

Creates the input graph as an adjacency matrix. Each entry represents the weight of the edge between nodes (graph[i][j]).
- Example: A weight of 999 is treated as "no direct connection" between nodes.
Takes input source node from the user.
Calls the dejkstra() function to calculate the shortest distance from the source node to all other nodes.
Prints the result for each node, showing the shortest distance from the source node.

Execution Example:

For the given graph:

graph = [
  [0, 3, 999, 7, 999],
  [3, 0, 4, 2, 999],
  [999, 4, 0, 5, 6],
  [7, 2, 5, 0, 4],
  [999, 999, 6, 4, 0]
]

If the input source is 0, the output would calculate the shortest distance from node 0 to all others:

Minimum distance from the source node is:
0 -----> 0 ====== 0
0 -----> 1 ====== 3
0 -----> 2 ====== 7
0 -----> 3 ====== 5
0 -----> 4 ====== 9

Observations and Limitations:

Hardcoded Infinity Value: The value 999 is hardcoded to indicate no connection. Ideally, this should be replaced with something like float('inf') for better clarity and correctness.
Global Lists: The visited and dist lists are global, which is not ideal. It can lead to unintended side effects when the function is reused with different inputs.
No Input Validation: The source input is directly taken from the user without validation; invalid inputs might break the program.
Inefficient Search for Minimum Distance: The search for the unvisited node with the smallest distance in the ecount loop has a time complexity of (O(n^2)). Using a priority queue (min-heap) could reduce this to (O((n + e) \log n)), where (e) is the number of edges.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr

This code implements **Dijkstra's shortest path algorithm** to find the...