[PYTHON] Full understanding of the concepts of Bellman-Ford and Dijkstra

Overview

We introduced the Dijkstra method and the Bellman-ford method at an in-house study session. At that time, I was researching various proofs of the algorithm, but I noticed that there were not many articles explained. I personally think that the question "Why does that happen?" Is an important factor, so I would like to introduce these algorithms with that in mind.

What kind of person is the writer?

Programming history: 1 year (Python only) Atcoder tea I have been working for a data analysis consignment company since April 2020, but for some reason I am just studying algorithms.

When do you use this algorithm?

Used to solve the single starting point shortest path problem of a weighted graph.

For each term, Weighted: Cost required to pass through the edge Single starting point: One starting point Shortest route: The route from the starting point to the destination at the lowest cost is.

Taking the graph below as an example The purpose is to find the shortest route from the starting point $ A $ to all sides. By the way, the shortest route from $ A to E $ is （A→D→B→F→E） is. We will find this using an algorithm.

Before the algorithm, the important properties of the graph

1. The shortest path is the shortest path

The partial road of the shortest road is the shortest road everywhere.

Proof
Temporarily, in the graph above, the shortest path of $ A → E $ （A→B→C→D→E　cost:5） will do.

Of these, $ (A → B → C cost: 3) $ Is a partial road of this shortest path, but if you use the apex B'for this section You can move the cost by 1 less. Then the shortest path in this section is （A→B'→C　cost:2） Therefore, $ A → E $ （A→B'→C→D→E　cost:4） It can be moved with, which contradicts the assumption. The partial road of the shortest road is always the shortest road.

2. Path relaxation

By finding the shortest paths in order from the vertices related to the start point, all the shortest paths are finally found. This is because, after all, the shortest path gradually obtained from the starting point becomes a partial path of the apex that reaches beyond that point.

What is the Bellman-Ford method?

Find the shortest path between all vertices. The major difference from Dijkstra's algorithm is that ** negative weights are allowed **.

The process of finding the shortest path is

1. Focus on all edges and update the value ** if you can reduce the cost of the vertices that pass through those edges **
2. Perform the process of 1. ** (number of vertices-1) times ** is.

In the figure below,

In process 1, you can start $ A $ and reach $ C $ at a cost of $ 5 $, so make a note of it as $ C: 5 $. Next, $ A → B $ can be reached at $ -1 $, so $ B: -1 $ and $ B → C $ can be reached at a cost of $ -1 + 2 = 1 $. At this time, I found that I could reach C at a smaller cost via $ B $, so I will update it to $ C: 1 $. Do this for all sides. This is the first time. After that, if you repeat (number of vertices-1) times, you can start from $ A $ and find the shortest path to all vertices.

Why do you do it (number of vertices-1) times?

The maximum number of vertices that pass from the start point to the destination is the vertices excluding the start point, that is, (number of vertices-1). In the process described above, the shortest path ** of the vertices that can be moved from the start point in the first loop) is always found. In the second loop, the shortest path (the vertex that can be moved from the route determined in the first time) is ** always ** found. ・ ・ ・ After all, this loop is the work of finding the shortest path in order starting from the starting point, so it is possible to find the shortest path by route relaxation.

If you are in trouble due to negative weight

See the figure below. The circled part is a cycle, but if you go around here, the cost will decrease by -2. In other words, if you use this cycle, you can reduce the cost infinitely. This is called ** negative cycle **.

The Bellman-Ford method can also detect negative cycles. Earlier, I confirmed that the shortest path is found in the loop (number of vertices-1) times, but the cost of all vertices is calculated again, and if there is a vertex whose cost can be updated, there is a negative cycle. Will be.

Show me the source code

It supports the input of the adjacency list format (there is also an adjacency matrix, which is often used in competition pros), and detects the shortest path by the Bellman-Ford method. Here is an example of an input with a negative cycle below the code (graph in the figure above). Replaces the cost of vertices through the negative cycle with $ -inf $.

def shortest_path(s,n,es):
    #The shortest distance from s to i
    # s:start point, n:Number of vertices, es[i]: [辺のstart point,Edge of edge,Edge cost]
    
    #Weight initialization. Make a note of the shortest distance here
    d = [float("inf")] * n
    
    #The starting point is 0
    d[s] = 0

    #Calculate the shortest path
    for _ in range(n-1):
        # es:About side i[from,to,cost]
        for p,q,r in es:
            #Updated if the root of the arrow has been searched and there is a costable route
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
    
    #Check the negative cycle
    for _ in range(n-1):
        # e:About side i[from,to,cost]
        for p,q,r in es:
            #Because the points to be updated are affected by the negative cycle-put inf
            if d[q] > d[p] + r:
                d[q] = -float("inf")
    return d
################
#input
n,w = map(int,input().split()) #n:Number of vertices w:Number of sides

es = [] #es[i]: [The starting point of the side,Edge of edge,Edge cost]
for _ in range(w):
    x,y,z = map(int,input().split())
    es.append([x,y,z])
    # es.append([y,x,z])

print(shortest_path(0,n,es))

'''
input
7 12
0 1 2 
0 2 -5
0 3 5
1 2 3
1 4 1
1 5 3
2 4 6
3 2 -2
3 5 4
4 6 -5
5 4 -2
6 2 -3
'''
>>[0, 2, -inf, 5, -inf, 5, -inf]

The amount of calculation is $ O (V ^ 2 + E) $ (number of vertices: $ V $, number of edges: $ E $).

What is Dijkstra's algorithm?

It can be used in graphs with non-negative weights.

The process of finding the shortest path is [Yobinori's video]( ) Is so easy to understand that it dies. (Yobinori's defensive range is too wide ...)

I will explain it here as well.

Let the cost of the vertex be (initial value: $ S = 0 $, other $ = ∞ $).

1. Start from the vertex with the lowest cost. Initially, $ S $ is the starting point.

2. Determine the cost of the starting point (green in the figure). The cost of this vertex will no longer be updated.

3. Make a note of the starting point cost + edge weights on the vertices that can be moved from the starting point. Noted $ 7, 3, 1 $ at the top of the middle row. The cost is uncertain as it may still be updated.

4. Repeat steps 1 to 3 until all vertices are confirmed. Of the vertices noted, the one with the cost of 1 is the smallest, so confirm it and note the vertices that can be moved from that vertex. If you can move at a lower cost, update the cost.

Why is the shortest path required?

** The vertex with the lowest cost among the undetermined vertices cannot be updated to a lower cost **. Since there are only non-negative weights, even if you take another route, the cost will be 0 or more. Therefore, of the undetermined, the smallest cost can be determined as the shortest path.

So what's the source code?

import heapq

def dijkstra(s, n, es):
    #The shortest distance from the start point s to each vertex
    #n:Number of vertices, cost[u][v] :Edge uv cost(Inf when it does not exist)
    d = [float("inf")] * n
    #Search list
    S = [s]
    #Priority queues reduce the amount of computation
    heapq.heapify(S)

    d[s] = 0
    
    while S:
        #Extract the peak of the lowest cost
        v = heapq.heappop(S)
        # print("-----------v", v)
        for u, w in es[v]:
            # print(u, w)
            #Update if reachable at a lower cost and add to list
            if d[u] > d[v]+w:
                d[u] = d[v]+w
                heapq.heappush(S, u)
        # print("d", d)
    return d

n,w = map(int,input().split()) #n:Number of vertices w:Number of sides

cost = [[float("inf") for i in range(n)] for i in range(n)] 
es = [[] for _ in range(n)]

for i in range(w):
    x, y, z = map(int, input().split())
    es[x].append([y, z])
    es[y].append([x, z]) #Delete this line for directed graphs
# print(es)
print(dijkstra(0, n, es))

References or sites

・ Algorithm Introduction 3rd Edition Volume 2: Advanced Design and Analysis Method ・ Advanced Data Structure ・ Graph Algorithm (World Standard MIT Textbook) (T. Colmen, R. Rivest, C. Stein, C. Riserson, Tetsuo Asano, Kazuo Iwano, Hiroshi Umeo, Masashi Yamashita, Koichi Wada) It's a fairly heavy book, but the proof of graph theory was very polite.

・ Graph theory ⑤ (Dijkstra's algorithm) ("University Mathematics / Physics" Learned at Preparatory School) https://www.youtube.com/watch?v=X1AsMlJdiok You can fully understand Dijkstra's algorithm just by watching this video!

・ Arimoto python Single shortest path method 2 (Dijkstra's algorithm) Competitive programming (For Juppy's blog and code, refer to here.) https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%8D%98%E4%B8%80%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%952%EF%BC%88%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%EF%BC%89_%E7%AB%B6%E6%8A%80%E3%83%97

bonus

The graph in the article was drawn with networkx. I'll put the code for those who care.

#Dijkstra's algorithm graph
import matplotlib.pyplot as plt
import networkx as nx

#Set of directed graphs
G = nx.DiGraph()

#Add edges
# G.add_edges_from([("A", "B", {"weight":2)])
# nx.add_path(G, ["A", "C"])
# G.edges["A", "B"]["weight"] = 2
G.add_weighted_edges_from([("A", "B", 5), ("A", "C", 7), ("A", "D", 1), ("B", "C", 3), ("B", "F", 3), ("D", "B", 2)])
G.add_weighted_edges_from([("C", "E", 3), ("D", "F", 8), ("F", "E", 2), ("B", "E", 6)])

#If you do not specify the coordinates of the vertices in the figure, they will be arranged randomly.
pos1 = {}
pos1["A"] = (0, 0)
pos1["B"] = (1, 0)
pos1["C"] = (1, 2)
pos1["D"] = (1, -2)
pos1["E"] = (2, 1)
pos1["F"] = (2, -1)

#If you draw it as it is, the weight character will be an obstacle, so erase it
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}

#Write weight
nx.draw_networkx_edge_labels(G, pos1, edge_labels=edge_labels, font_size=18)
#Drawing
nx.draw_networkx(G, pos1, node_size=1000, label_pos=100, node_color="r", font_size=18)
#Save figure
plt.savefig("dijkstra.png ")
plt.show()

#Dijkstra's algorithm is also implemented in networkx. Computational complexity is O(V^2+E)So slow
pred, dist = nx.dijkstra_predecessor_and_distance(G, "A")
print(pred, dist)

>>{'A': [], 'B': ['D'], 'C': ['B'], 'D': ['A'], 'F': ['B'], 'E': ['F']} 
>>{'A': 0, 'D': 1, 'B': 3, 'C': 6, 'F': 6, 'E': 8}