# Python Program to Implement Dijkstra’s Shortest Path Algorithm

«
»

This is a Python program to implement Dijkstra’s Shortest Path algorithm on a graph.

Problem Description

The problem is to find the shortest distance to all vertices from a source vertex in a weighted graph.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function dijkstra that takes a Graph object and a source vertex as arguments.
3. The function begins by creating a set unvisited and adding all the vertices in the graph to it.
4. A dictionary distance is created with keys as the vertices in the graph and their value all set to infinity.
5. distance[source] is set to 0.
6. The algorithm proceeds by finding the vertex that has the minimum distance in the set unvisited.
7. It then removes this vertex from the set unvisited.
8. Then all the neighbours of this vertex that have not been visited yet have their distances updated.
9. The above steps repeat until the set unvisited becomes empty.
10. The dictionary distance is returned.
11. This algorithm works for both undirected and directed graphs.

Program/Source Code

Here is the source code of a Python program to implement Dijkstra’s Shortest Path algorithm on a graph. The program output is shown below.

```class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}

"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex

def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]

def __contains__(self, key):
return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with given weight."""

def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}

def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key

def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight

def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()

def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]

def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to

def dijkstra(g, source):
"""Return distance where distance[v] is min distance from source to v.

This will return a dictionary distance.

g is a Graph object.
source is a Vertex object in g.
"""
unvisited = set(g)
distance = dict.fromkeys(g, float('inf'))
distance[source] = 0

while unvisited != set():
# find vertex with minimum distance
closest = min(unvisited, key=lambda v: distance[v])

# mark as visited
unvisited.remove(closest)

# update distances
for neighbour in closest.get_neighbours():
if neighbour in unvisited:
new_distance = distance[closest] + closest.get_weight(neighbour)
if distance[neighbour] > new_distance:
distance[neighbour] = new_distance

return distance

g = Graph()
print('Undirected Graph')
print('add edge <src> <dest> <weight>')
print('shortest <source vertex key>')
print('display')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do
if operation == 'add':
suboperation = do
if suboperation == 'vertex':
key = int(do)
if key not in g:
else:
elif suboperation == 'edge':
src = int(do)
dest = int(do)
weight = int(do)
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
else:

elif operation == 'shortest':
key = int(do)
source = g.get_vertex(key)
distance = dijkstra(g, source)
print('Distances from {}: '.format(key))
for v in distance:
print('Distance to {}: {}'.format(v.get_key(), distance[v]))
print()

elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()

print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()

elif operation == 'quit':
break```
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. To find all shortest distances from a source vertex, dijkstra is called on the graph and the source vertex.

Runtime Test Cases
```Case 1:
Undirected Graph
add edge <src> <dest> <weight>
shortest <source vertex key>
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add vertex 5
What would you like to do? add vertex 6
What would you like to do? add vertex 7
What would you like to do? add edge 1 2 10
What would you like to do? add edge 1 3 80
What would you like to do? add edge 3 4 70
What would you like to do? add edge 2 5 20
What would you like to do? add edge 2 3 6
What would you like to do? add edge 5 6 50
What would you like to do? add edge 5 7 10
What would you like to do? add edge 6 7 5
What would you like to do? shortest 1
Distances from 1:
Distance to 6: 45
Distance to 3: 16
Distance to 4: 86
Distance to 5: 30
Distance to 2: 10
Distance to 7: 40
Distance to 1: 0

What would you like to do? quit

Case 2:
Undirected Graph
add edge <src> <dest> <weight>
shortest <source vertex key>
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add edge 1 2 10
What would you like to do? add edge 2 3 20
What would you like to do? add edge 3 4 30
What would you like to do? add edge 1 4 100
What would you like to do? shortest 1
Distances from 1:
Distance to 2: 10
Distance to 4: 60
Distance to 3: 30
Distance to 1: 0```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Participate in Python Programming Certification Contest of the Month Now! 