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.
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.
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
The partial road of the shortest road is the shortest road everywhere.
Proof
Temporarily, in the graph above, the shortest path of $ A → E $
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
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.
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
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.
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.
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.
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 $).
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.
Let the cost of the vertex be (initial value: $ S = 0 $, other $ = ∞ $).
Start from the vertex with the lowest cost. Initially, $ S $ is the starting point.
Determine the cost of the starting point (green in the figure). The cost of this vertex will no longer be updated.
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.
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.
** 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.
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))
・ 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
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}
Recommended Posts