Bellman-Ford algorithm for finding the shortest path from a source node to all other nodes in a graph. :param graph: the graph :param source: the source node :return: a dictionary containing the shortest path from the source node to all other nodes
(graph, source)
| 1 | # implementation of bellman-ford algorithm |
| 2 | def bellman_ford_algorithm(graph, source): |
| 3 | """ |
| 4 | Bellman-Ford algorithm for finding the shortest path from a source node to all other nodes in a graph. |
| 5 | :param graph: the graph |
| 6 | :param source: the source node |
| 7 | :return: a dictionary containing the shortest path from the source node to all other nodes |
| 8 | """ |
| 9 | # initialize distance of source to 0 |
| 10 | distance = {node: float('inf') for node in graph} |
| 11 | distance[source] = 0 |
| 12 | # relax edges repeatedly |
| 13 | for _ in range(len(graph) - 1): |
| 14 | for node in graph: |
| 15 | for neighbour in graph[node]: |
| 16 | if distance[node] + graph[node][neighbour] < distance[neighbour]: |
| 17 | distance[neighbour] = distance[node] + graph[node][neighbour] |
| 18 | # check for negative-weight cycles |
| 19 | for node in graph: |
| 20 | for neighbour in graph[node]: |
| 21 | if distance[node] + graph[node][neighbour] < distance[neighbour]: |
| 22 | print('Graph contains a negative-weight cycle') |
| 23 | return |
| 24 | return distance |
| 25 | |
| 26 | # example |
| 27 | if __name__ == '__main__': |