다익스트라, 플로이드-와샬 알고리즘

 

다익스트라
- 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘이다.
- 다익스트라 알고리즘의 핵심을 최단거리는 최단거리와 최단거리의 합으로 표현될 수 있다는 것이다.
  이런 이유로 다익스트라는 현재까지 알고 있는 최단거리를 계속 갱신해나가는 방법으로 구현된다. 
- 현재 최단거리 테이블에 저장된 최단거리는 지금까지 방문한 모든 노드를 고려했을 때, 최단 거리가 된다. 따라서 한번 방문한 노드를 다시 방문할 필요가 없다.
- 다익스트라 알고리즘은 음의 값을 가지는 케이스에서는 사용할 수 없다. 음의 값을 가지는 노드가 있을 경우, 그 노드를 여러번 방문하는 것이 가장 최단 거리가 작아지는 현상이 발생하기 때문이다.

다익스트라 알고리즘 방법
1. 먼저 출발 노드를 설정한다.
2. 현재 위치에서 갈 수 있는 모든 노드에 대한 최단거리를 업데이트 해준다. 최단거리의 업데이트는 가고자 하는 노드에 이미 저장되어있는 최단 거리와 현재 노드까지의 최단거리에 다음 노드까지 가는 비용을 더한 후 적은 값을 업데이트 해준다.
3. 현재 노드를 방문처리 해준다.
4. 다음 방문할 노드를 찾는데, 방문할 노드는 방문하지 않은 노드 중 최단거리가 가장 짧은 노드다. 
이 때, 조상님이 노드를 찾아주지 않기 때문에 선형 탐색으로 찾게 되며, 이 때 시간복잡도가 복잡해진다.
5. 해당 노드를 거쳐 다음 노드를 가는 경우에 대한 최소값을 모두 업데이트 해준다. 위의 방법을 반복해준다. 

다익스트라는 방문해야 할 노드를 찾는 과정에서 선형 탐색을 사용하기 때문에 시간복잡도가 증가하여 비효율적으로 바뀐다. 이 문제를 개선하기 위한 방법은 우선순위 힙을 이용하는 것이다. 



플로이드-와샬 알고리즘
- 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.
- 플로이드-와샬 알고리즘은 각 정점을 기준으로 각 최단 거리를 업데이트 해주는 방식으로 진행되는 알고리즘이다.
- 다익스트라 알고리즘과 동일한 값이 나오지만, 문제는 시간복잡도가 다익스트라보다 더 열화된다. 

플로이드-와샬 알고리즘 방법
1. 기본 상태에서 갈 수 있는 모든 노드의 값을 업데이트 해준다.
2. 1이라는 정점을 거쳐가는 것으로 가정을 하고, 1이라는 정점을 거쳐갔을 때 나머지 모든 정점으로 최단 거리가 짧아질 수 있는지를 확인한다. 예를 들어 1 → 2에 대한 최단 거리를 업데이트 할 때, 1→3, 3→2로 가는 각각의 최단 거리를 더한 다음 그 값이 더 짧을 경우 업데이트를 해준다.

플로이드-와샬 알고리즘에서 한 정점에 대해서 정리를 해준다는 것은 지금까지의 최단거리는 해당 노드를 거치는 것을 고려했을 때에도 최단거리라는 것을 의미한다. 따라서, 한번만 정리를 해주면 되고 다른 노드를 거쳐서 방문되는 것은 신경쓰지 않아도 된다. 

플로이드-와샬 예제, 백준 11404

i!=j를 하는 이유는 문제에서 '시작도시와 도착도시가 같은 경우는 없다'라는 기술이 나왔기 때문이다. 즉, 1에서 1로 가는 버스는 없다. 따라서 1에서 3, 3에서 1로 다시 오는 경우도 없는 것으로 판정하기 위해서 해당 조건이 들어가게 되었다. 

import sys
INF = 9876543210

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
d = [ [INF for _ in range(n+1)] for _ in range(n+1)]
for p in range(m) :
    a,b,c = map(int,sys.stdin.readline().split())
    if d[a][b] > c :
        d[a][b] = c


for k in range(1,n+1) :
    for i in range(1, n+1) :
        for j in range(1, n+1) :
            if i == j :
                continue
            else :
                if d[i][j] > d[i][k] + d[k][j] :
                    d[i][j] = d[i][k] + d[k][j]

for i in range(1,n+1) :
    for j in range(1,n+1) :
        if d[i][j] == 9876543210 :
            d[i][j] = 0

for i in range(1,n+1) :
    for j in range(1,n+1) :
        print(d[i][j], end= ' ')
    print()