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 37 38 39 40 41 42 43 44 45 46 47 48 49 50

import math from typing import List from collections import defaultdict
def bellman_ford(vertexs: int, edges: List[List[int]], origin: int, destination: int): ''' print shortest path from origin to destination Args: vertexs: number of vertexs. First vertex is 0. edges: list of (start, end, weight) origin:  destination:  Raise: ValueError: if destination is not reachable from origin or a negative cycle is found ''' dist, prev = defaultdict(lambda: math.inf), [None] * vertexs dist[origin] = 0 for _ in range(vertexs): upd = 0 for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w prev[v] = u upd += 1 if upd == 0: break for u, v, w in edges: if dist[u] + w < dist[v]: raise ValueError('Negative cycle is found') path, cur = [], destination while cur != origin and prev[cur] is not None: path.append(cur) cur = prev[cur] if cur != origin: raise ValueError(f'{destination} is not reachable from {origin}') path = [origin] + path[::1] print('>'.join([str(vertex) for vertex in path]))
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 1]], 0, 4)
bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 1], [2, 4, 10], [3, 4, 1], [4, 1, 1]], 0, 4)
