The below program contains error please help to solve it. from collections import deque def find_shortest_paths(graph): paths = {} vertices = graph.keys() for start_vertex in vertices: visited = set() distances = {vertex: float('inf') for vertex in vertices} distances[start_vertex] = 0 queue = deque([(start_vertex, [])]) while queue: current_vertex, path = queue.popleft() visited.add(current_vertex) for neighbor in graph[current_vertex]: if neighbor not in visited: distances[neighbor] = min(distances[neighbor], distances[current_vertex] + 1) queue.append((neighbor, path + [current_vertex])) for end_vertex in vertices: paths[(start_vertex, end_vertex)] = set(path + [end_vertex] for path in paths[(start_vertex, end_vertex)] + [path] if len(path) == distances[end_vertex]) return paths def find_largest_set(paths): largest_set = set() for u, v in paths: for w in paths: if u != v and u != w and v != w and len(paths[u, v]) != len(paths[u, w]) + len(paths[w, v]): break else: if len(paths[u, v]) > len(largest_set): largest_set = paths[u, v] return largest_set # Example 1 graph1 = { 'A': ['B', 'C', 'D', 'F'], 'B': ['A', 'C', 'D', 'F'], 'C': ['A', 'B', 'D', 'F'], 'D': ['A', 'B', 'C', 'E', 'F'], 'E': ['D', 'F'], 'F': ['A', 'B', 'C', 'D', 'E'] } paths1 = find_shortest_paths(graph1) largest_set1 = find_largest_set(paths1) print("The largest set is:") print(largest_set1) print("The cardinality is:", len(largest_set1)) print() # Example 2 graph2 = { '1': ['2', '5', '6'], '2': ['1', '3', '7'], '3': ['2', '4', '8'], '4': ['3', '5', '9'], '5': ['1', '4', '10'], '6': ['1', '8', '9'], '7': ['2', '9', '10'], '8': ['3', '6', '10'], '9': ['4', '6', '7'], '10': ['5', '7', '8'] } paths2 = find_shortest_paths(graph2) largest_set2 = find_largest_set(paths2) print("The largest set is:") print(largest_set2) print("The cardinality is:", len(largest_set2))
The below program contains error please help to solve it.
from collections import deque
def find_shortest_paths(graph):
paths = {}
vertices = graph.keys()
for start_vertex in vertices:
visited = set()
distances = {vertex: float('inf') for vertex in vertices}
distances[start_vertex] = 0
queue = deque([(start_vertex, [])])
while queue:
current_vertex, path = queue.popleft()
visited.add(current_vertex)
for neighbor in graph[current_vertex]:
if neighbor not in visited:
distances[neighbor] = min(distances[neighbor], distances[current_vertex] + 1)
queue.append((neighbor, path + [current_vertex]))
for end_vertex in vertices:
paths[(start_vertex, end_vertex)] = set(path + [end_vertex] for path in paths[(start_vertex, end_vertex)] + [path] if len(path) == distances[end_vertex])
return paths
def find_largest_set(paths):
largest_set = set()
for u, v in paths:
for w in paths:
if u != v and u != w and v != w and len(paths[u, v]) != len(paths[u, w]) + len(paths[w, v]):
break
else:
if len(paths[u, v]) > len(largest_set):
largest_set = paths[u, v]
return largest_set
# Example 1
graph1 = {
'A': ['B', 'C', 'D', 'F'],
'B': ['A', 'C', 'D', 'F'],
'C': ['A', 'B', 'D', 'F'],
'D': ['A', 'B', 'C', 'E', 'F'],
'E': ['D', 'F'],
'F': ['A', 'B', 'C', 'D', 'E']
}
paths1 = find_shortest_paths(graph1)
largest_set1 = find_largest_set(paths1)
print("The largest set is:")
print(largest_set1)
print("The cardinality is:", len(largest_set1))
print()
# Example 2
graph2 = {
'1': ['2', '5', '6'],
'2': ['1', '3', '7'],
'3': ['2', '4', '8'],
'4': ['3', '5', '9'],
'5': ['1', '4', '10'],
'6': ['1', '8', '9'],
'7': ['2', '9', '10'],
'8': ['3', '6', '10'],
'9': ['4', '6', '7'],
'10': ['5', '7', '8']
}
paths2 = find_shortest_paths(graph2)
largest_set2 = find_largest_set(paths2)
print("The largest set is:")
print(largest_set2)
print("The cardinality is:", len(largest_set2))
![Q
ננו
LD
5
$
C
C
JS
GO
php
main.py
38
39 # Example 1
40 graph1 = {
41
42
43
44
45
46
47 }
48
49
paths1 = find_shortest_paths (graph1)
50 largest set1 = find_largest_set(paths1)
51
52 print("The largest set is:")
53 print (largest_set1)
54 print("The cardinality is:", len(largest_set1))
55 print()
56
T
'A':
['B', 'C', 'D', 'F'],
'B': ['A', 'C', 'D', 'F'],
'C': ['A', 'B', 'D', 'F'],
'D': ['A', 'B', 'C', 'E', 'F'],
'E': ['D', 'F'],
'F': ['A', 'B', 'C', 'D', 'E']
57 # Example 2
58 graph2 = {
59
60
'1': ['2', '5', '6'],
['1'
॥੨॥
-יכי
וידי
c
Run
Shell
^ ERROR!
Traceback (most recent call last):
File "<string>", line 49, in <module>
File "<string>", line 23, in find_shortest_paths
KeyError: ('F', 'A')
Clear](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F389196b2-0e91-4920-9348-30d387d059ce%2Fdd732384-2386-435a-be87-f4133a567ade%2Ff99d6ug_processed.png&w=3840&q=75)
Step by step
Solved in 5 steps with 3 images
