说明

从某个点出发，求最短路径算法, 可以有负权路径，带路径

模版

class Graph:
    def __init__(self, vertices):
        self.M = vertices   # Total number of vertices in the graph
        self.graph = []     # Array of edges

    # Add edges
    def add_edge(self, a, b, c):
        self.graph.append([a, b, c])

    def bellman_ford(self, src):
        distance = [float("Inf")] * self.M
        distance[src] = 0
        for i in range(self.M+1):
            for a, b, c in self.graph:
                if distance[a] != float("Inf") and distance[a] + c < distance[b]:
                    if i == self.M:
                        # 出现环了，可以无限减少
                        return -1 
                    distance[b] = distance[a] + c