다익스트라 알고리즘

설명

 

코드

inf = 100
dist = [
    [0,3,2,inf, inf, 8],
    [3,0,inf,inf, 9,1],
    [2,inf,0,4,inf,5],
    [inf,inf,4,0,3,inf],
    [inf,9,inf,3,0,inf],
    [8,1,5,inf,inf, 0]
]
 
n = 6
#prev = [[0]* n for _ in range(n) ]
 
def find_minidx(src,temp):
    tmp = inf
    idx = 0
    for i in temp:
        cur = dist[src][i]
        if i!=src and cur<tmp:
            tmp = cur
            idx = i
    return idx
 
def dijkstra(src,n):
    temp = [i for i in range(n)]
    temp.remove(src)
    while temp:
        idx = find_minidx(src, temp)
        temp.remove(idx)
        for neighbor in range(n):
            if dist[idx][neighbor]==inf:
                continue
            alt = dist[src][idx]+dist[idx][neighbor]
            if alt<dist[src][neighbor]:
                dist[src][neighbor] = alt
                #prev[src][neighbor] = idx
 
for i in range(n):
    dijkstra(i,n)
 
for i in range(n):
    print(dist[i])
 

Before Dijkstra                                                                              After Dijkstra