Restoring Shortest Path
BFS searching shortest path
That was hard! But now let's implement a method to find the shortest path between two vertices, not only length.
To do that, you have to know for each node where did it come from. So, let's add list pred that contains predcessor for i node. At the beginning, pred contains only -1.
Uppgift
Swipe to start coding
Modify bfs(start, end) so it returns a list of vertices between start and end nodes (both inclusive). If there is no path, return an empty list.
Do not forget to keep the path.
Var allt tydligt?
Tack för dina kommentarer!
Avsnitt 2. Kapitel 4
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Graph:
def __init__(self, vertices):
# init graph with its vertices
self.graph = {v : [] for v in vertices}
def addEdge(self, u, v):
self.graph[u].append(v)
def __str__(self):
out = ""
for vertex in self.graph:
out += vertex + ":"+self.graph[vertex]
return out
def bfs(self, start, end):
q = [] # queue
# list of predcessors: pred[i] contains the parent node
pred = [-1 for _ in self.graph.keys()]
visited = [-1 for v in self.graph.keys()]
q.append(start)
visited[start] = 0
while len(q)>0:
node = q.pop(0)
for vertex in self.graph[node]: # iterate neighbors, update q, visited and pred
# put your code here
return _________
g=Graph([0,1,2,3,4,5])
g.addEdge(0,1)
g.addEdge(2,1)
g.addEdge(1,0)
Fråga AI
Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal
