Purpose

Find the shortest distance from one vertex to another. (Single starting point shortest path) ** Can be used even if there is an edge with a negative cost **.

principle

Let the number of vertices of the graph be $ V $ and the number of edges be $ E $. Create a list $ d $ that records the minimum cost for each vertex. Here, the distance to one's own point is fixed at 0, and the distance to another point is INF. From here, look at all the sides and update the shortest distance. Specifically, if the edge $ e $ has the information cost $ cost $ from vertex $ from $ to vertex $ to , $d[from] + cost < d[to]$$ When, the value of $ d [to] $ is updated to $ d [from] + cost $. A total of $ V -1 $ times to look at all edges will determine all minimum costs in the absence of a negative cycle. In other words, if the minimum cost is still updated at the $ V $ th time, it has a negative cycle, so the correct minimum cost cannot be obtained. So why is it okay to complete the operation in a $ V -1 $ loop? Explain how to understand yourself. The same vertex will never be included in the least costly path to a vertex. If it is included, there is a negative cycle, so the correct route cannot be found in the first place. From the above, the maximum number of edges included in the shortest path to a certain vertex is $ V -1 $. As you can see by checking the code after this, the order of the sides is the input order. (It does not search in the order of closeness like breadth-first search.) In other words, consider the process of finding the shortest path of $ V -1 $. Hopefully, one loop will follow the edges in order from the front, and this shortest path may be found. However, suppose that the order of the sides to be examined is neatly arranged from the back. At this time, if the front side is not examined, the side after that cannot be considered as a part of the shortest path. (Because the distance to $ from $ is not INF or the minimum cost) In other words, in this case, only one of the shortest paths can be found for each loop. So this is the worst case, requiring $ V -1 $ loops.

In that case, I implemented it with the intention of searching in order of breadth-first search, but if there is a negative cycle, the value will continue to be updated indefinitely, so I felt that it was necessary to devise that. When it was only a positive cost, I threw it into the Dijkstra problem on Aizu Online and it was the correct answer, so I wonder if it has a name.

Computational complexity analysis

In the worst case, the operation to see all edges is performed $ V -1 $ times, so the amount of calculation is $ O (EV) $.

Implementation

# O(EV)
def bellman_ford(s):
    d = [float('inf')]*n #Minimum cost to each vertex
    d[s] = 0 #Distance to self is 0
    for i in range(n):
        update = False #Was the update done?
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        #There is a negative cycle
        if i == n - 1:
            return -1
    return d

n, w = [int(x) for x in input().split()] # n:Number of vertices, w:Number of sides
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] #start point,end point,cost
    g.append([x, y, z])
    g.append([y, x, z]) #Deleted in directed graph
print(bellman_ford(0))

in conclusion

Regarding the code, this time I'm pretty worried about the way of thinking, so please advise if you like!

References

Programming Contest Challenge Book