Algorithm in Python (Dijkstra's algorithm)

Introduction

I would like to study the contents of the library, which I had only pasted until now, little by little. The reason for writing this article is that I would like to confirm my thoughts and give advice, so please comment! (Especially speeding up, computational complexity)

Purpose

Find the shortest distance from one starting point to another vertex for a graph with no negative cost edges. (Single starting point shortest path)

principle

Consider the case where the number of vertices of the graph is $ V $ and the number of edges is $ E $. First, prepare two lists. One is to record the shortest distance from the starting point, and the other is to record whether the shortest path has been determined. (It seems that it can be combined into one, but it is the same as when understanding it.) Here, the distance to your own point is fixed at 0, and the distance to other points is INF. Prepare a priority queue to retrieve the minimum value for the cost of an edge. Then, the side extending from its own point is put in the priority queue. At this time, ** with respect to the destination of the edge with the minimum cost, there is no lower cost via other edges **. Because the cost is non-negative, it will be a detour. Therefore, the side with the minimum cost is extracted, and the shortest distance to the apex of this destination is determined. Furthermore, the edges extending from this apex are also put in the priority queue in the same way. The distance is ** the distance to this vertex + the cost of the side **. Here, since the side having the destination for which the shortest distance is fixed is not related to the shortest distance, the amount of calculation becomes lighter if it is not included. Repeat the above process until all the shortest distances are determined. (Implementation keeps the priority queue empty)

Implementation

import heapq
def dijkstra(s):
    #The shortest distance from the start point to each vertex
    d = [float('inf')]*n
    d[s] = 0
    #Whether each vertex has been visited
    used = [False]*n
    used[s] = True
    #Heap to record temporary distance
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        u, v = heapq.heappop(que)
        if used[v]:
            continue
        d[v] = u
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

input

n = 4
g = [[[1, 1], [4, 2]], [[1, 0], [2, 2], [5, 3]], [[4, 0], [2, 1], [1, 3]], [[1, 2], [5, 1]]] #Adjacency list
print(dijkstra(0))

output

[0, 1, 3, 4]

Computational complexity analysis

Addition to the priority queue is $ O (E) $ depending on the number of edges. The size of the priority queue is proportional to $ V $ by not including the edges unless they are the shortest distance, so each operation is $ O (logV) $. Therefore, the amount of calculation is $ O (ElogV) $.

Question

I wondered if the size of the priority queue is proportional to the number of sides $ E $, but I was a little reluctant to prun it in proportion to $ V $. If you write it down concretely, you can see that it will never reach $ E $, but I would like you to tell me if you can easily express it with some mathematical formula. In the first place, when the edges are stretched between all the vertices, it becomes $ E∝V ^ 2 $, which is worse than other $ O (V ^ 2) $ algorithms, so I don't think it is necessary to think about it!

Concrete example

The above example. We will select and update the one with the lowest cost among the vertices that can be reached. 94790.jpg

in conclusion

I would like to update it as a memorandum in the future. I'm more motivated because the articles are sometimes used as references.

References

[Programming Contest Challenge Book](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F% E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% AC% AC2% E7% 89 % 88-% EF% BD% 9E% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E6% B1% BA% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% B4% BB% E7% 94% A8% E5% 8A% 9B% E3% 81% A8% E3% 82% B3% E3% 83% BC% E3% 83% 87% E3% 82% A3% E3% 83% B3% E3% 82% B0% E3% 83% 86% E3% 82% AF% E3% 83% 8B% E3% 83% 83% E3% 82% AF% E3% 82% 92% E9% 8D% 9B% E3% 81% 88% E3% 82% 8B% EF% BD% 9E-% E7% A7 % 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89-ebook / dp / B00CY9256C) [Juppy's blog](https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3 % 82% A4% E3% 82% AA% E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AD% E3% 83% A5% E3% 83% BC% 28heapq% 29 % E3% 82% 92% E7% 94% A8% E3% 81% 84% E3% 81% 9F% E3% 83% 97% E3% 83% AA% E3% 83% A0% E6% B3% 95)

Recommended Posts

Algorithm in Python (Dijkstra's algorithm)
Genetic algorithm in python
Algorithm in Python (Bellman-Ford)
Ant book in python: Sec.2-5 Dijkstra's algorithm
Algorithm in Python (primality test)
Python algorithm
Reproduce Euclidean algorithm in Python
Algorithm in Python (binary search)
[Python3] Dijkstra's algorithm with 14 lines
Algorithm in Python (breadth-first search, bfs)
Sorting algorithm and implementation in Python
Write A * (A-star) algorithm in Python
Algorithm in Python (depth-first search, dfs)
Implementing a simple algorithm in Python 2
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Python memorandum (algorithm)
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Disassemble in Python
Reflection in Python
Constant in python
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Algorithm in Python (ABC 146 C Binary Search
Write a simple greedy algorithm in Python
Alignment algorithm by insertion method in Python
Sorted list in Python
Clustering text in Python