Dijkstras’s algorithm or shortest path algorithm is for finding the shortest path between two nodes in a graph which represents a map or distances between places.

The algorithm requires 3 inputs: distance matrix, source node and destination node. The implementation of algorimth is as follows:

1. Start from source node.
2. Check distances of all nodes which are connected from source, select the node with least distance from source.
3. Check distance from this temporary node to its all connected nodes and select the node with least distance.
4. Now repeat this process untill destination is reached.

In the following code, the list src2dist list is used for storing all the distances of the nodes which are connected to source. visited list is used to keep track of which nodes are visited which are not. 9999 specifies a infinite path from src to that particular node.

import math
def dijkstra(distances,src,dst):
	num_cities = int(math.sqrt(len(distances)))
	src2dist = [9999 for i in range(0, num_cities)]
	visited = [0 for i in range(0, num_cities)]
	tmp_start = src
	visited[src] = 1
	src2dist[src] = 0
	
	while (visited[dst] == 0):
		min_edge = 9999
		min_node = -1
		for i in range(0, num_cities):
			d = src2dist[tmp_start] + distances[(tmp_start*num_cities)+i]
			if (d < src2dist[i] and visited[i] == 0):
				src2dist[i] = d
			if (min_edge > src2dist[i] and visited[i] == 0):
				min_edge = src2dist[i]
				min_node = i
		tmp_start = min_node
		visited[tmp_start] = 1
	print ("The smallest distance between source and destination is:"src2dist[dst])
	
distances = input("Enter distance matrix separated by spaces:").split(" ")
distances = [int(x) for x in distances]
src_dst = input("Enter source and destination separated by space:").split(" ")
src = int(src_dst[0])
dst = int(src_dst[1])
dijkstra(distances,src,dst)

Output:

Download code from here