[알고리즘] ASP(1) - 모든 쌍의 최단 경로 ( All Pairs Shortest Path )

1. 모든 쌍의 최단 경로( All Pairs Shortest Path )

이전 글의 주제로 단일 출발지 최단 경로( SSP )를 알아보았습니다.

SSP는 출발점 하나에 대해서 모든 정점까지의 최단 경로를 구하는 것이였습니다.

SSP의 대표적인 알고리즘으로 Bellman-Ford 알고리즘 , Dijkstra's 알고리즘이 있었습니다.

이번 주제는 모든 쌍의 최단 경로( ASP )입니다.

ASP는 모든 정점이 출발점이 되어 모든 정점에 대해 최단 경로를 구하는 것입니다.

ASP는 모든 정점이 출발점이자 어떤 최단 경로상의 한 정점입니다.

예를 들어,  v1 -> v2 -> v4 -> v5 라는 v1 -> v5의 최단 경로가 존재하며 v3 -> v2 -> v4 라는 최단 경로가 존재할 수 있습니다.

물론 SSP에서 출발 점을 바꿔가면서 Bellman-Ford 알고리즘이나 Dijkstra's 알고리즘을 통해 모든 쌍의 최단 경로를 구현할 수 있습니다.

그런데 SSP의 시간복잡도는 매우 느리다는 것을 알고 있습니다.

Bellman - Ford 알고리즘의 시간 복잡도    :  

Dijkstra's 알고리즘의 시간 복잡도            :   

( Prim's알고리즘 Dijkstra's 알고리즘에서 언급을 안했지만 최소 우선순위 큐를 구현하는 가장 성능이 좋은 자료구조는 Fibonacci heap 입니다. )

간선의 개수 | E |, 정점의 개수 | V |에 대해 을 만족하고,

정점의 개수 만큼 각 알고리즘 수행해서 ASP를 구현해야 하므로 시간복잡도는 다음과 같이 변할 것입니다.

Bellman - Ford 알고리즘의 시간 복잡도            :  

Dijkstra's 알고리즘의 시간 복잡도(binary heap)   :  

따라서 SSP를 여러번 수행해서 ASP를 구현하는 것은 바람직하지 못합니다.

그래서 ASP을 구현할 때는 인접행렬이라는 다른 방법을 사용합니다.

2. 인접행렬

인접행렬을 라고 할 때 인접행렬의 각 원소는 입니다.

( i는 행 , j는 열을 의미합니다. )

인접행렬의 각 행과 열의 개수는 각각 정점의 개수만큼 존재하며, 정점에 대응됩니다.

인접행렬은 위와 그림과 같이 정점 간의 최단 경로를 표현할 수 있습니다.

행과 열은 모두 정점에 대응되므로, 정점 i에서 정점 v까지의 비용은 가 됩니다.

예를들어 v1 -> v3의 최단 경로의 비용은 8이고, v4 -> v3의 최단 경로의 비용은 -5입니다.

또한 선행자 인접행렬을 만들어서 모든 쌍의 최단 경로 자체를 구할 수도 있습니다.

ASP의 대표적인 알고리즘은 Shortest Paths and Matrix Multiplication 과 Floyd-warshall 알고리즘이 있습니다.

이 두 알고리즘 모두 인접행렬을 이용하여 구현할 수 있습니다.

이상으로 ASP와 ASP를 구현하는데 사용되는 인정행렬에 대해 알아보았습니다.

이어지는 글에서 Shortest Paths and Matrix Multiplication 과 Floyd-warshall 알고리즘에 대해 알아보도록 하겠습니다.