최단 경로 문제_다익스트라, 플로이드 와샬 알고리즘

다익스트라 알고리즘

하나의 노드로부터 다른 노드까지의 최단경로 탐색 알고리즘으로 O(v^2)의 시간복잡도를 가졌다. 우선순위큐(힙트리)방식을 이용하면 O((V+E)logV) (v = 노드 수, E 간선수)의 시간복잡도를 가지게 된다.

 

조건 

그래프 방향의 유무는 상관없으나 간선들중 가중치가 음수이면 사용이 불가하다.

 

현실세계에서도 음수의 가중치가 존재하지 않으므로 GPS소프트웨어 등에서 가장 많이 사용된다고 한다. 

(음의 가중치를 가지는 간선이 있으면서 가중치 합이 음인 사이클이 존재하지 않는다면 벨만포드 알고리즘을 사용 가능하다.)

작동원리

1. 출발노드설정
2. 출발노드기준 인접노드까지의 가중치 저장 연결되지 않은 노드 무한대
3. 방문하지 않은 노드중 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐 다음 인접노드로 가는경우 고려하여 가중치를 비교 최소가중치로 갱신
5. 3,4번의 과정 반복

출처 : https://youtu.be/HFapeLxvdNg

---

플루이드 와샬 알고리즘

각 정점간 최단경로를 탐색시 사용된다.

음수 가중치를 가지더라도 사이클이 없다면 처리된다. 

 

시간복잡도는 3개의 반목문을 통해 O(V^3)이다.

 

구현 

플로이드 와샬 알고리즘은 반복문을 통해

배열[i][j] > 배열[i][k] + 배열[k][j]  일 경우  배열[i][j] = 배열[i][k] + 배열[k][j]을 해주면된다.

INF = float('inf')

def main():
    n, m = map(int, input().split())
    distance = [[INF for _ in range(n+1)] for _ in range(n+1)]

    for i in range(m):
        src, dst, cost = map(int, input().split())
        if distance[src][dst] > cost: # 이미 간선 정보가 주어진 정점일 때
            distance[src][dst] = cost
    
    for i in range(1, n+1):
        distance[i][i] = 0

    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if distance[i][k] + distance[k][j] < distance[i][j]: # 거쳐가는 길이 더 작은 길일때 갱신
                    distance[i][j] = distance[i][k] + distance[k][j]
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            if distance[i][j] == INF: # 갈 수 없는 경우 0으로
                print(0, end = " ")
            else:
                print(distance[i][j], end = " ")
        print("")

if __name__ == "__main__":
    main()

 

 

 

참고
https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 개념 유튜브 https://youtu.be/HFapeLxvdNg

다익스트라, 플루이드 비교 https://codedoc.tistory.com/95 

https://mygumi.tistory.com/110