최단 경로와 다익스트라 알고리즘

  • 최단 경로 문제: Revisited
    • 모든 정점의 쌍에 대한 최단 경로 구하기 (플로이드 알고리즘)
    • 단일 정점에서 모든 다른 정점으로의 최단경로 구하기 (다익스트라 알고리즘)

다익스트라 알고리즘 슈도 코드

1
2
3
4
5
6
7
8
9
Y = {v1};
F = ∅
while (답을 구하지 못함):
    Y에 속한 정점만 중간에 거쳐 가는 정점으로 하여
        v1에서 최단경로를 가진 정점 v를 V - Y에서 선택한다
    새로운 정점 v를 Y에 추가한다
    최단경로 상에서 v로 가는 간선을 F에 추가한다
    if(Y == V):
        답을 구했으니 return
  • W[i][j]: 그래프 G의 인접행렬
  • touch[i]: Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 현재 최단경로 상의 마지막 간선을 (v, vi)라고 할 때, Y에 속한 정점 v의 인덱스
  • length[i]: Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 현재 최단 경로의 길이

파이썬으로 다익스트라 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def dijkstra (W):
    n = len(W) - 1
    F = []
    touch = [-1] * (n + 1)
    length = [-1] * (n + 1) 
    for i in range(2, n+1):
        touch[i] = 1
        length[i] = W[1][i]

    for _ in range(n - 1):
        minValue = INF
        for i in range(2, n + 1):
            if(0 <= length[i] and length[i] < minValue):
                minValue = length[i]
                vnear = i
        edge = (touch[vnear], vnear, W[touch[vnear]][vnear])
        F.append(edge)
        for i in range(2, n + 1):
            if (length[i] > length[vnear] + W[vnear][i]):
                length[i] = length[vnear] + W[vnear][i]
                touch[i] = vnear
        length[vnear] = -1
    return F

def length (F):
    total = 0
    for e in F:
        total += e[2] # (1, 5, 1) 처럼 들어오기 때문에 가중치는 index 2번에 있음
        return total