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 image.png 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
image.png 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,

image.png

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. image.png 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 $.

Click to see
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](![Image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/411380/a8c60f68-abfc- d92b-02bb-b915e8b8da19.png) ) Is so easy to understand that it dies. (Yobinori's defensive range is too wide ...)

I will explain it here as well. image.png

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?

Click to see
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))
The original complexity is $ O (V ^ 2) $, which is the same as the Bellman-Ford algorithm, but it can be reduced to $ O ((E + V) logV) $ by using the priority queue.

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.

Click to see
#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}

Recommended Posts

Full understanding of the concepts of Bellman-Ford and Dijkstra
Full understanding of Python threading and multiprocessing
Python asynchronous processing ~ Full understanding of async and await ~
Full understanding of Python debugging
Understanding the meaning of complex and bizarre normal distribution formulas
The story of Python and the story of NaN
Understanding and implementing the Tonelli-Shanks algorithm (2)
[Python] Understanding the potential_field_planning of Python Robotics
Understanding and implementing the Tonelli-Shanks algorithm (1)
This and that of the inclusion notation.
A rough understanding of python-fire and a memo
Review the concept and terminology of regression
The story of trying deep3d and losing
About the behavior of copy, deepcopy and numpy.copy
The answer of "1/2" is different between python2 and 3
Organize the meaning of methods, classes and objects
Specifying the range of ruby and python arrays
Change the color of Fabric errors and warnings
Compare the speed of Python append and map
[Python] A rough understanding of the logging module
General description of the CPUFreq core and CPUFreq notifiers
Organize the super-basic usage of Autotools and pkg-config
I read and implemented the Variants of UKR
[Python] A rough understanding of iterators, iterators, and generators
About the * (asterisk) argument of python (and itertools.starmap)
A discussion of the strengths and weaknesses of Python
The nice and regrettable parts of Cloud Datalab
Get the title of yahoo news and analyze sentiment
The story of Python without increment and decrement operators.
Automatically determine and process the encoding of the text file
relation of the Fibonacci number series and the Golden ratio
The process of installing Atom and getting Python running
Python --Explanation and usage summary of the top 24 packages
Visualize the range of interpolation and extrapolation with python
[FSL] Measurement of segment and volume of the basal ganglia
Think about the next generation of Rack and WSGI
Mathematical understanding of principal component analysis from the beginning
Referencing and changing the upper bound of Python recursion
I checked out the versions of Blender and Python
Techniques for understanding the basis of deep learning decisions
I checked the default OS and shell of docker-machine
Visualization of the connection between malware and the callback server
[Django 2.2] Sort and get the value of the relation destination
Get an abstract understanding of Python modules and packages
Personal notes about the integration of vscode and anaconda
Check the type and version of your Linux distribution
Animate the basics of dynamic programming and the knapsack problem