[PYTHON] Finding the shortest path of a graph with a cycle by breadth-first search is sometimes faster than Dijkstra's algorithm, but in the worst case it is slower.

The shortest path of a graph with a cycle (= not a tree) is also found at high speed using breadth-first search ...!?

https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d

When I solved this AtCoder's past question, I was able to do AC using Dijkstra's algorithm, but with Python (PyPy), the execution time limit (2000ms) is just barely reached. When I searched for past submissions, I found a fast answer of 789ms while there were many over 1000ms.

https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/7721902

It does something like breadth-first search for a tree, but if the graph has a cycle instead of a tree, the time complexity appears to be $ O (V ^ 2) $ (if it is a tree). $ O (V) = O (E) $). However, the answer is actually fast. Considering the possibility that the estimation of the amount of calculation is wrong, I compared the following three methods.

- dijkstra0 </ b>: A method like breadth-first search of the above link (partially modified, should be $ O (V ^ 2) ) - dijkstra1 : Dijkstra's algorithm using priority queue ( O ((E + V) \ log {V}) ) - dijkstra2 : The most basic Dijkstra method ( O (V ^ 2) $)

Reference: <a href=https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3 % 83% A9% E6% B3% 95> Wikipedia article pseudocode

Considering only the time complexity, dijkstra1 </ b> seems to be the fastest in many cases.

Problem setting

Use concatenated undirected graphs ($ V $ vertices, $ E $ edges, no multiple edges, no self-loops). First, create a straight road that passes through all the points once in order from the start point, as shown in the figure below, to ensure the connection (the order of the vertices along the way is random). The other edges are randomly stretched between vertices that have no edges yet. Edge weights are randomly determined from $ 1 $ to $ 10 ^ 7 $ for each edge.

$V \in \{ 10^3,~ 10^4,~ 10^5,~ 10^6,~ 10^7 \} $ $E \in \{ 10^3,~ 10^4,~ 10^5,~ 3\cdot 10^5,~ 10^6,~ 10^7 \} $ (The reason why I put $ 3 \ cdot 10 ^ 5 $ in the number of sides is because I assumed the restrictions of the competition pro)

Time was measured for $ (V, E) $ satisfying $ V-1 \ leqq E \ leqq \ frac {V (V-1)} {2} $.

code

worstcase.py


def dijkstra0(a, in_connect_list, v, money_kind): 
    out_shortest_list = [10**15 for i in range(v)]   #Distance from vertex a
    out_shortest_list[a] = 0
    searching_list = [a]
    
    while searching_list != []:
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                c = j[0]
                p = j[money_kind] 
                if out_shortest_list[c] > p + out_shortest_list[i]:
                    out_shortest_list[c] = p + out_shortest_list[i]
                    new_search_list.append(c)
        searching_list = list(set(new_search_list))  #Change from original code
    return out_shortest_list


def dijkstra1(s, M):
    D = [10**15] * v  #Distance from vertex s
    D[s] = 0
    V = [0] * v  #D at the apex[i]1 if is determined to be the shortest distance
    Q = []  #Priority queue
    for v in range(v):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        heapq.heappush(Q, [alt, v])
    return D


def dijkstra2(s, M):
    D = [10**15] * v  #Distance from vertex s
    D[s] = 0
    Q = [i for i in range(v)]
    
    while len(Q) > 0:
        mi_ind = -1
        mi = 10**15
        for i in Q:
            if D[i] < mi:
                mi = D[i]
                mi_ind = i
        Q.pop(Q.index(mi_ind))
        for i in range(len(M[mi_ind])):
            v = M[mi_ind][i][0]
            luv = M[mi_ind][i][1]
            D[v] = min(D[v], D[mi_ind] + luv)
    return D


from random import randint, random, sample
import heapq
import time

V = [10**3, 10**4, 10**5, 10**6, 10**7]
E = [10**3, 10**4, 10**5, 3 * 10**5, 10**6, 10**7] 

for v in V:
    for e in E:
        if v-1 <= e <= v*(v-1)//2:  #Conditions for concatenation and no multiple edges
            T = []
            for _ in range(10):  #Take the average measured 10 times
                
                N_shuf = [0] + sample([i for i in range(1, v)], v-1)
                M = [[] for i in range(v)]

                A = [min(N_shuf[i],N_shuf[i+1]) * v
                     + max(N_shuf[i],N_shuf[i+1]) for i in range(v-1)]
                while len(A) < e:
                    e_add = e - len(A)
                    ADD = [0] * e_add
                    i = 0
                    while i < e_add:
                        v0 = randint(0, v-1)
                        v1 = randint(0, v-1)
                        if v0 != v1:
                            ADD[i] = min(v0,v1) * v + max(v0,v1)
                            i += 1
                    A += ADD
                    A = list(set(A))  #Remove multiple edges

                for ii in A:
                    i = ii // v
                    j = ii % v
                    M[i].append([j, randint(1, 10**7)])
                    M[j].append([i, randint(1, 10**7)])

                t0 = time.time()
                
                D = dijkstra0(0, M, v, 1)
                # D = dijkstra1(0, M)
                # D = dijkstra2(0, M)

                t1 = time.time() - t0
                T.append(t1)
            print(v, e, sum(T) / 10)

result

The average of 10 times, the unit was seconds, and 2 significant figures.

- dijkstra0 </ b>: A method like breadth-first search ($ O (V ^ 2) $)

V \ E 10^3 10^4 10^5 3\cdot 10^5 10^6 10^7
10^3 0.00060 0.0074 0.14 0.40
10^4 0.0069 0.29 0.96 3.1 25
10^5 0.13 1.0 4.4 53
10^6 1.6 75
10^7 18

- dijkstra1 </ b>: Dijkstra's algorithm using priority queue ($ O ((E + V) \ log {V}) $)

V \ E 10^3 10^4 10^5 3\cdot 10^5 10^6 10^7
10^3 0.0016 0.0059 0.070 0.23
10^4 0.020 0.16 0.41 1.1 8.9
10^5 0.36 1.3 2.6 15
10^6 4.4 37
10^7 53

- dijkstra2 </ b>: The most basic Dijkstra method ($ O (V ^ 2) $)

V \ E 10^3 10^4 10^5 3\cdot 10^5 10^6 10^7
10^3 0.017 0.023 0.11 0.29
10^4 1.9 2.1 2.2 3.1 14
10^5 180 - - -
10^6 - -
10^7 -

-: Not measured because it took more than a few hundred seconds

Consideration

The most basic Dijkstra method is clearly slower as $ V $ increases. However, the dijkstra0 </ b> and priority queue method ( dijkstra1 </ b>) does not seem to make a big difference within the scope of the table. If the conditions are likely to be in a competition pro ($ V \ leqq 10 ^ 5, ~ E \ leqq 3 \ cdot 10 ^ 5 $), either one will pass, or in some cases dijkstra0 </ b> will be better. It also seems to be fast (time comparisons are given in the table below). Another feature of dijkstra0 </ b> is that if you fix $ E $ and increase $ V $, it may be faster. Apparently, dijkstra0 </ b> is sparse and close to a tree (= $ V $ is large but $ E $ is small) and is good at graphs. If it is close to a tree, it will be almost $ O (V) $.

Table below: Ratio of time required ( dijkstra0 </ b> / dijsktra1 </ b>)

V \ E 10^3 10^4 10^5 3\cdot 10^5 10^6 10^7
10^3 0.38 1.3 2.0 1.7
10^4 0.35 1.8 2.4 2.8 2.8
10^5 0.37 0.82 1.7 3.6
10^6 0.36 2.0
10^7 0.34

In the worst case ...

The following graph can be considered as the worst case of dijkstra0 </ b>. The number of updates of the shortest distance is $ (V-1) $ times for the upper left vertex, $ (V-2) $ times for the one to the right, ..., $ 1 $ for the upper right vertex. Since the total number of updates is $ \ frac {V (V-1)} {2} $ times, the calculation time will increase almost in proportion to $ V ^ 2 $. Rewrite the code other than the function part of Dijkstra's algorithm as follows, $ V \ in \ {10 ^ 3, ~ 5 \ cdot 10 ^ 3, ~ 10 ^ 4, ~ 5 \ cdot 10 ^ 4 \} $ I compared it with.

worstcase.py


from random import randint, random, sample
import heapq
import time

for v in [1000, 5000, 10000, 50000]:
        T = []
        for _ in range(10):

            N_shuf = [0] + sample([i for i in range(1, v)], v-1)
            M = [[] for i in range(v)]

            for i in range(1, v):
                M[0].append([N_shuf[i], 10**7 - i * 2])
                M[N_shuf[i]].append([0, 10**7 - i * 2])
            for i in range(1, v-1):
                M[N_shuf[i+1]].append([N_shuf[i], 1])
                M[N_shuf[i]].append([N_shuf[i+1], 1])

            t0 = time.time()
            D = dijkstra0(0, M, v, 1)
            # D = dijkstra1(0, M)
            # D = dijkstra2(0, M)
            t1 = time.time() - t0
            T.append(t1)
        print(v, sum(T) / 10)
V E dijkstra0 dijkstra1 dijkstra2
1000 1997 0.11 0.0024 0.017
5000 9997 3.1 0.016 0.45
10000 19997 12 0.033 1.8
50000 99997 740 0.25 48

After all, in dijkstra0 </ b>, when $ V $ is multiplied by 10, the calculation time will be 100 to 200 times (this is also the case with dijkstra2 </ b>). The result is completely different. dijkstra1 </ b>, which is $ O ((E + V) \ log {V}) $, is still stable and fast. There may be cases where this worst case is not included in the test case as in the problem at the beginning, but it seems better to use dijkstra1 </ b> in the competition pro. In the case of the time limit, it is better to deal with it by implementing a fast-moving implementation including parts other than Dijkstra's algorithm.

Summary

--When breadth-first search for trees is used for a graph with a cycle, the time complexity is $ O (V ^ 2) , but the Dijkstra method is devised ( O ((E + V) \ log {V}) $. ) May be faster. ――For graphs that are about the size of a competition pro, you may pass. ――But in the worst case, it is slow, so it is better to use Dijkstra's method.

Change log

--2020/04/20 Changed article title (old title: O (V ^ 2) is faster than Dijkstra? Breadth-first search for graphs with closed paths), partially revised