Dijkstras Alogrithm – Python

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:
dijkstras
Download code from here

Advertisements

About Anuroop D

Very enthusiastic about technology and likes to share my knowledge through blogging. Has Bachelor's in Information Technology and currently pursuing my Master's in Computer Science.
This entry was posted in Python and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s