[PYTHON] Trouver le chemin le plus court sur un graphe avec un chemin fermé est parfois plus rapide que la méthode Dyxtra, mais dans le pire des cas, c'est plus lent.

Problème de réglage

Utilisez un graphe concaténé non orienté ($ V $ pour les sommets, $ E $ pour les côtés, pas de côtés multiples, pas d'auto-boucle). Tout d'abord, comme le montre la figure ci-dessous, en créant une route unique qui traverse tous les points une fois dans l'ordre à partir du point de départ, la connexion est garantie (l'ordre des sommets le long du chemin est aléatoire). Les autres côtés sont étirés au hasard entre des sommets qui n'ont pas encore de côtés. Le poids des côtés est déterminé aléatoirement de 1 $ à 10 $ ^ 7 $ pour chaque côté.

$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 \} $ (La raison pour laquelle j'ai mis $ 3 \ cdot 10 ^ 5 $ dans le nombre de côtés est parce que j'ai assumé les restrictions de la concurrence pro)

Le temps a été mesuré pour $ (V, E) $ satisfaisant $ 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 du sommet 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))  #Changement du code d'origine
    return out_shortest_list


def dijkstra1(s, M):
    D = [10**15] * v  #Distance des sommets s
    D[s] = 0
    V = [0] * v  #D à ce sommet[i]Si est déterminée comme étant la distance la plus courte 1
    Q = []  #File d'attente de priorité
    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 des sommets 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 de concaténation et pas de côtés multiples
            T = []
            for _ in range(10):  #Prendre la moyenne mesurée 10 fois
                
                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))  #Supprimer plusieurs côtés

                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)

résultat

La moyenne de 10 fois, l'unité était de secondes et 2 nombres valides.

• dijkstra0 </ b>: une méthode comme la recherche de priorité de largeur ($ 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)