[PYTHON] Das Finden des kürzesten Pfades eines Diagramms mit einem geschlossenen Pfad nach Breitenprioritätssuche ist manchmal schneller als die Dyxtra-Methode, im schlimmsten Fall jedoch langsamer.

Problemstellung

Verwenden Sie ein verkettetes ungerichtetes Diagramm ($ V $ für Eckpunkte, $ E $ für Seiten, keine Mehrfachseiten, keine Selbstschleife). Erstellen Sie zunächst eine gerade Straße, die alle Punkte einmal in der Reihenfolge vom Startpunkt aus durchläuft, wie in der folgenden Abbildung gezeigt, um die Verbindung sicherzustellen (die Reihenfolge der Scheitelpunkte auf dem Weg ist zufällig). Die anderen Seiten werden zufällig zwischen Eckpunkten gestreckt, die noch keine Seiten haben. Das Gewicht der Seiten wird zufällig von $ 1 $ bis $ 10 ^ 7 $ für jede Seite bestimmt.

$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 \} $ (Der Grund, warum ich $ 3 \ cdot 10 ^ 5 $ in die Anzahl der Seiten gesetzt habe, ist, dass ich die Einschränkungen des Wettbewerbsprofis übernommen habe)

Die Zeit wurde für $ (V, E) $ gemessen, das $ V-1 \ leqq E \ leqq \ frac {V (V-1)} {2} $ erfüllt.

Code

worstcase.py

def dijkstra0(a, in_connect_list, v, money_kind): 
    out_shortest_list = [10**15 for i in range(v)]   #Abstand von der Spitze 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))  #Änderung vom ursprünglichen Code
    return out_shortest_list


def dijkstra1(s, M):
    D = [10**15] * v  #Abstand von Eckpunkten s
    D[s] = 0
    V = [0] * v  #D an dieser Spitze[i]If wird als kürzeste Entfernung bestimmt 1
    Q = []  #Prioritätswarteschlange
    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  #Abstand von Eckpunkten 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:  #Bedingungen für die Verkettung und keine Mehrfachseiten
            T = []
            for _ in range(10):  #Nehmen Sie den 10-mal gemessenen Durchschnitt
                
                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))  #Entfernen Sie mehrere Seiten

                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)

Ergebnis

Der Durchschnitt von 10 Mal war die Einheit Sekunden und 2 gültige Zahlen.

• dijkstra0 </ b>: Eine Methode wie die Suche nach Breitenpriorität ($ O (V ^ 2) $)

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)