최단 경로와 플로이드 알고리즘

• 엄밀한 문제 정의:
  ⁃ G = (V, E): G는 그래프, V는 정점(vertex)의 집합, E는 간선(edge)의 집합
  ⁃ 그래프 G는 방향성(directed), 가중치(weighted) 그래프임
  ⁃ 최단 경로는 단순 경로(simple path): 같은 정점을 두 번 거치지 않음(acyclic)

• 재귀 관계식 구하기
  • D0 = W, Dk는 Dk−1로부터 구함 (1 ≤ k ≤ n)

• Dk−1[i][j]: vi에서 vj로 k − 1개의 중간 정점을 지남

• Dk[i][j]: 다음과 같은 두 가지의 경우를 고려
⁃ 경우 1: 하나의 정점을 더 지나게 해 줘도 새로운 최단 경로가 없는 경우
• Dk[i][j] = Dk−1[i][j]

⁃ 경우 2: 하나의 정점(vk)을 더 지나면 새로운 최단 경로가 있는 경우
• Dk[i][j] = Dk−1[i][k] + Dk−1[k][j]

python 코드

정의

def floyd (W):
  D = W
  n = len(W)
  for k in range(n):
    for i in range(n):
      for j in range(n):
        D[i][j] = min(D[i][j], D[i][k] + D[k][j])
  return D

INF = 999
W = [

[0, 1, INF, 1, 5],
[9, 0, 3, 2, INF],
[INF, INF, 0, 4, INF],
[INF, INF, 2, 0, 3],
[3, INF, INF, INF, 0]

]

D = floyd(W)
for i in range(len(D)):
  print(D[i])

최단경로 정의

def floyd2 (W):
  n = len(W)
  D = W
  P = [[-1] * n for _ in range(n)]
  for k in range(n):

    for i in range(n):

      for j in range(n):

        if (D[i][j] > D[i][k] + D[k][j]):
          D[i][j] = D[i][k] + D[k][j]
          P[i][j] = k

  return D, P

최단 경로 출력

def path (P, u, v):
  if (P[u][v] != -1):
    path(P, u, P[u][v])
    print('v%d'%(P[u][v]), end=
    '-> ')
    path(P, P[u][v], v)
D, P = floyd2(W)
for i in range(len(D)):
  print(D[i])
for i in range(len(P)):
  print(P[i])

u = 4
v = 2
print('shortest path from v%d to v%d:'%(u, v), end=
' ')

print('v%d'%(u), end='-> ')

path(P, u, v)
print('v%d'%(v), end=' ')