[알고리즘] All-Pair-Shortest-Path Problem

Problem definition: Can we print all the vertices in the shortest path?

• Step 1: Change/add codes in Slide 18 to print out all the vertices in the shortest path from $𝑣_𝑠$ to $𝑣_𝑑$ (HINT: Modify min function)

  INF = int (1e9 + 7)
  
  def floyd_warshall(dist, length):
  		for r in range(length):
  				for p in range(length):
  						for q in range(length):
  								dist[p][q] = min(dist[p][q], dist[p][r] + dist[r][q])
  		print_dist(dist, length)
  
  def print_dist(dist, length):
  		for p in range(length):
  				temp=""
  				for q in range(length):
  						if(dist[p][q] == INF):
  								temp += "INF "
  						else:
  								temp += str(dist[p][q])+"  "
  				print(temp+" ")
  
  # test code
  W=[[0, 4,1 1],
  		[6, 0, 2],
  		[3, INF, 0]]
  floyd_warshall(W, len(W[0]))

• Step 2: Use the following input

  W = [ [ 0, 3, INF, 7 ],
  			[ 8, 0, 2, INF ],
  			[ 5, INF, 0, 1 ],
  			[ 2, INF, INF, 0 ] ]

• Step 3: Print out all the vertices on two shortest paths, ($𝑣_1$, $𝑣_3$) and ($𝑣_0$, $𝑣_2$)

Step1

INF = int(1e9 + 7)

def floyd_warshall(W, length):
    dist = [[W[i][j] for j in range(length)] for i in range(length)]
    nxt = [[-1] * length for _ in range(length)]

    for i in range(length):
        for j in range(length):
            if W[i][j] != INF and i != j:
                nxt[i][j] = j

    for r in range(length):
        for p in range(length):
            for q in range(length):
                if dist[p][r] + dist[r][q] < dist[p][q]:
                    dist[p][q] = dist[p][r] + dist[r][q]
                    nxt[p][q] = nxt[p][r]

    print_dist(dist, length)
    return dist, nxt

def print_dist(dist, length):
    print("=== Shortest Distance Matrix ===")
    for p in range(length):
        temp = ""
        for q in range(length):
            if dist[p][q] >= INF:
                temp += "INF\t"
            else:
                temp += str(dist[p][q]) + "\t"
        print(temp)
    print()

def get_path(nxt, u, v):
    if nxt[u][v] == -1:
        return []
    
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path

최단 경로를 갱신할 때마다 어떤 노드를 거쳐가는 것이 최적인지를 기억하는 nxt 2차원 배열을 추가로 선언했다. min() 함수 대신 if 조건문을 사용하여 더 짧은 경로가 발견될 때마다 거리와 다음 방문 노드를 동시에 갱신하도록 코드를 수정했다.

Step2

제시된 그래프 W를 입력값으로 넣고, $v_1$에서 $v_3$까지의 경로와 $v_0$에서 $v_2$까지의 최단 경로를 출력하는 테스트 코드이다.

# test code
W = [ [ 0,   3, INF,   7 ],
      [ 8,   0,   2, INF ],
      [ 5, INF,   0,   1 ],
      [ 2, INF, INF,   0 ] ]

dist, nxt = floyd_warshall(W, len(W[0]))

path_1_3 = get_path(nxt, 1, 3)
path_0_2 = get_path(nxt, 0, 2)

print("=== Shortest Paths ===")
print(f"Shortest path from v1 to v3: {path_1_3} (Distance: {dist[1][3]})")
print(f"Shortest path from v0 to v2: {path_0_2} (Distance: {dist[0][2]})")

Step3

실행 결과는 다음과 같다.

=== Shortest Distance Matrix ===
0	3	5	6	
6	0	2	3	
3	6	0	1	
2	5	7	0	

=== Shortest Paths ===
Shortest path from v1 to v3: [1, 2, 3] (Distance: 3)
Shortest path from v0 to v2: [0, 1, 2] (Distance: 5)