This is a Python program to find shortest path from a vertex to all vertices using BFS in an unweighted graph.

The program creates a graph object and allows the user to find the shortest path from a vertex to all nodes.

1. Create classes for Graph, Vertex and Queue.

2. Create a function find_shortest_paths that takes a Vertex object called src as argument.

3. The function begins by creating an empty set called visited and a Queue object, q.

4. It also creates a dictionary parent which maps each vertex to its parent in the BFS tree. src is mapped to None.

5. It also creates a dictionary distance that maps each vertex to the shortest distance between src and that vertex. src is mapped to 0.

6. It enqueues the passed Vertex object and also adds it to the set visited.

7. A while loop is created which runs as long as the queue is no empty.

8. In each iteration of the loop, the queue is dequeued and all of its neighbours are enqueued which have not already been visited.

9. In addition to enqueuing, they are also added to the set visited, parent of each of the neighbours is set to the dequeued node, and distance of each neighbour is set to one plus the distance of the dequeued node.

10. After the loop is finished, the dictionaries parent and distance are returned as a tuple.

11. This algorithm also works for undirected graphs. In an undirected graph, whenever edge (u, v) is added to the graph, the reverse edge (v, u) is also added.

Here is the source code of a Python program to find the shortest path from a source node to all nodes using BFS in an unweighted graph. The program output is shown below.

class Graph: def __init__(self): # dictionary containing keys that map to the corresponding vertex object self.vertices = {} def add_vertex(self, key): """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.""" self.vertices[src_key].add_neighbour(self.vertices[dest_key], 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 # dictionary containing destination vertices mapped to the weight of the # edge with which they are joined to this vertex 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 class Queue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def enqueue(self, data): self.items.append(data) def dequeue(self): return self.items.pop(0) def find_shortest_paths(src): """Returns tuple of two dictionaries: (parent, distance) parent contains vertices mapped to their parent vertex in the shortest path from src to that vertex. distance contains vertices mapped to their shortest distance from src. """ parent = {src: None} distance = {src: 0} visited = set() q = Queue() q.enqueue(src) visited.add(src) while not q.is_empty(): current = q.dequeue() for dest in current.get_neighbours(): if dest not in visited: visited.add(dest) parent[dest] = current distance[dest] = distance[current] + 1 q.enqueue(dest) return (parent, distance) g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('shortest <vertex key>') print('display') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0] if operation == 'add': suboperation = do[1] if suboperation == 'vertex': key = int(do[2]) if key not in g: g.add_vertex(key) else: print('Vertex already exists.') elif suboperation == 'edge': src = int(do[2]) dest = int(do[3]) 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): g.add_edge(src, dest) else: print('Edge already exists.') elif operation == 'shortest': key = int(do[1]) src = g.get_vertex(key) parent, distance = find_shortest_paths(src) print('Path from destination vertices to source vertex {}:'.format(key)) for v in parent: print('Vertex {} (distance {}): '.format(v.get_key(), distance[v]), end='') while parent[v] is not None: print(v.get_key(), end = ' ') v = parent[v] print(src.get_key()) # print source vertex 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

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 the shortest paths from a source vertex, find_shortest_paths is called.

4. The dictionary parent is used to print the path while the dictionary distance is used to print the distance from a particular vertex to the source vertex.

Case 1: Menu add vertex <key> add edge <src> <dest> shortest <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 edge 1 2 What would you like to do? add edge 2 3 What would you like to do? shortest 1 Path from destination vertices to source vertex 1: Vertex 1 (distance 0): 1 Vertex 3 (distance 2): 3 2 1 Vertex 2 (distance 1): 2 1 What would you like to do? add edge 1 3 What would you like to do? shortest 1 Path from destination vertices to source vertex 1: Vertex 1 (distance 0): 1 Vertex 3 (distance 1): 3 1 Vertex 2 (distance 1): 2 1 What would you like to do? quit Case 2: Menu add vertex <key> add edge <src> <dest> shortest <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? shortest 1 Path from destination vertices to source vertex 1: Vertex 1 (distance 0): 1 What would you like to do? add edge 1 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 edge 2 3 What would you like to do? add edge 2 4 What would you like to do? add edge 4 5 What would you like to do? add edge 4 6 What would you like to do? shortest 1 Path from destination vertices to source vertex 1: Vertex 5 (distance 3): 5 4 2 1 Vertex 6 (distance 3): 6 4 2 1 Vertex 3 (distance 2): 3 2 1 Vertex 2 (distance 1): 2 1 Vertex 1 (distance 0): 1 Vertex 4 (distance 2): 4 2 1 What would you like to do? add edge 2 6 What would you like to do? add edge 1 5 What would you like to do? shortest 1 Path from destination vertices to source vertex 1: Vertex 5 (distance 1): 5 1 Vertex 6 (distance 2): 6 2 1 Vertex 3 (distance 2): 3 2 1 Vertex 2 (distance 1): 2 1 Vertex 1 (distance 0): 1 Vertex 4 (distance 2): 4 2 1 What would you like to do? quit

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Python Books
- Check Information Technology Books
- Practice Programming MCQs
- Apply for Programming Internship
- Apply for Python Internship