# Program To Create a Function Number of Shortest Paths in Python Assignment Solution

June 28, 2024
Dr. David
🇦🇺 Australia
Python
Dr. David Adams, a distinguished Computer Science scholar, holds a PhD from the University of Melbourne, Australia. With over 5 years of experience in the field, he has completed over 300 Python assignments, showcasing his deep understanding and expertise in the subject matter.
Key Topics
• Instructions
• Objective
• Requirements and Specifications
Tip of the day
News

## Instructions

### Objective

Write a python homework to create a function number of shortest paths.

## Requirements and Specifications

This problem you will implement the first part of the Girvan Newman Algorithm. That is, given a source vertex, source, determine, for each vertex v the number of shortest paths starting at the source that pass-through v. You may not use any imports besides the queue module for this problem. Define a function called number_of_shortest_ paths that will take as input a vertex label called source and a graph G. The function will return a dictionary whose keys are the vertices in G and the values will be the number of shortest paths in G that begin at the source and pass through those vertices. You may want to consider the following strategy. The idea is to modify the code for the breadth-first search so that when a vertex is discovered you will store its level in the BFS presentation that begins at the source as part of its value in G. The other part of the value will be the vertices with a level one lower than itself that are adjacent to it. To begin you can assign the source a level of 0. Generally, if a vertex is discovered by a vertex with level m it will have level m + 1. For a vertex at level m + 1 you will also need to store 1 the vertices at level m that are adjacent to it. Using this information, you can calculate the number of shortest paths by starting at the highest level and working backwards. A vertex that does not discover any new vertices has only one shortest path passing through it. This information can be sent back level by level to determine the number of shortest paths for each vertex. Note that the source should have a value which is equal to the total number of vertices in the graph. Here we consider the path with just one vertex to be the shortest path from the source to itself.

Source Code

```#!/usr/bin/env python3 # -*- coding: utf-8 -*- import queue def number_of_shortest_paths(source, G): '''1. Maintain two dictionaries. One that stores the level of each vertex and another that stores, for each vertex, the vertices one level lower that connects to it. 2. Maintain a list of the vertices that do not discover any new vertices. 3. Maintain a queue as in the BFS algorithm. 4. Loop while the queue is not empty as in the BFS. Gather the necessary data for the collections in parts 1 and 2 5. Create a dictionary to store the number of shortest paths for each vertex. Give each end vertex a value of 1. 6. Get a collection of all vertices and sort it based on level. The vertices with the highest level should come first. So the source should be in this list. 7. Loop through the sorted collection. For each vertex add one to the value for each vertex that connected to it from one level lower. You will have to make sure that keys are in the dictionary when adding one to their value. 8. Return the dictionary from part 5.''' levels = {source : 0} queue = [source] visited = [source] result = {} max_level = 0 while len(queue) > 0: curr = queue.pop(0) max_level = max(max_level, levels[curr]) for next in G[curr]: if next not in visited: visited.append(next) queue.append(next) levels[next] = levels[curr] + 1 for i in range(max_level + 1): for v in levels: if levels[v] == i: if i == 0: result[v] = 0 else: counter = 0 for w in levels: if levels[w] == i-1 and v in G[w]: counter += 1 result[v] = counter return result if __name__ == '__main__': G = {0 : {1 : 1, 2 : 1}, 1 : {2 : 1, 3 : 1}, 2 : {3 : 1}, 3 : {0 : 1, 4 : 1}, 4 : {0 : 1}} print(number_of_shortest_paths(0, G)) ```

## Similar Samples

Looking for expert programming homework help? At ProgrammingHomeworkHelp.com, we specialize in providing high-quality solutions for Java, Python, C++, and more. Our team of experienced programmers ensures accurate and timely delivery of assignments, tailored to your specific requirements. Whether you're struggling with basic syntax or tackling advanced algorithms, we're here to assist you every step of the way. Visit our website for sample solutions and experience our commitment to your academic success firsthand.