blob: a0f315c2dc699ff81b737b0804ffd6185d1fa590 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import notebooks.Graph as Graph
from collections import defaultdict
from heapq import heappush, heappop
import math
def dijkstra(adjacency_list, source_id, target_id):
""" To be implemented by students. `adjacency_list` is a dictionary with structure:
{node_id: [...(neighbor_id, weight)]}.
Function should return (distance, path). Path should be a list of the nodes in the shortest path
**including** the source_id and target_id. If no shortest path is found, it should return (infinity, []) """
return math.inf, [source_id]
if __name__ == '__main__':
try:
Graph.test_dijkstra(dijkstra)
print('Passed ALL tests!')
except AssertionError:
print('Failed one or more tests')
|
