선행 지식

• 그래프의 이해

설명

플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이다.

알고리즘은 다음과 같은 과정으로 이루어진다:

1. 그래프의 인접 행렬을 초기화한다.
2. 정점 i에서 정점 j로의 직접 경로가 있는 경우, 인접 행렬의 i행 j열을 해당 경로의 가중치로 설정한다.
3. 인접 행렬을 이용하여 모든 정점 쌍 사이의 최단 경로를 구한다. 이를 위해서는 다음의 두 가지 경우를 비교한다:
   • i에서 j로의 직접 경로가 존재하는 경우, 해당 경로의 가중치를 사용한다.
   • i에서 j로의 경로가 존재하지 않는 경우, i를 거쳐 j로 가는 경로를 고려한다. 이때, i에서 k로 가는 경로와 k에서 j로 가는 경로의 가중치를 합한 값이 i에서 j로 가는 경로의 가중치보다 작으면, 인접 행렬의 i행 j열을 해당 값으로 갱신한다.

플로이드 워셜 알고리즘은 시간 복잡도 O(n^3)으로, 그래프의 크기가 작을 때 유용하게 사용될 수 있다.

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if graph[i][j]:
                dist[i][j] = graph[i][j]

    for k in range(n): # 0~N까지 한개씩 집음           
        for i in range(n):# 0~N노드중 k노드로 연결된걸 찾음
            for j in range(n):# K노드에서 0~N노드중 연결된걸 찾음
                if dist[i][j] > dist[i][k] + dist[k][j]: # 만약 i 노드와 k가 연결 돼 있고 k노드와 j노드가 연결 돼 있다면 & i -> k -> j의 경로가 원래 i -> j의 경로보다 짧다면
                    dist[i][j] = dist[i][k] + dist[k][j] # i노드와 j 노드도 연결 된 것
																												 # 최단거리 갱신
    return dist

반복문 순서로 거쳐가는 노드가 제일 밖에 있어야 모든 노드 탐색이 되니 꼭 명심.

예시 문제

1번.

11403번 경로 찾기