[~ to Many] Dijkstra Algorithm & Floyd Warshall Algorithm

1. 개요

Dijkstra Algorithm과 Floyd Warshall Algorithm을 이용하는 이유가 무엇일까? MST의 kruskal Algo. 와 Prim. Algo 와는 다른 점이 무엇일까?

MST의 경우엔, 모든 vertex를 방문할 수 있는 최단 경로를 나타낸다. 

반면 Dijkstra는 하나의 vertex에서 다른 vertex까지의 최단 경로를 나타낸다.

Floyd Warshll은 한 vertex에서 다른 vertex까지의 모든 최단 경로를 알아내고자 사용하는 알고리즘이다.

 

따라서, Dijkstra는 O(n^2)의 시간 복잡도를, Floyd Warshall은 O(n^3)의 시간 복잡도를 가진다.

 

아래 코드에서 Floyd Warshall 알고리즘을 Bellman Ford 알고리즘으로 잘못 적었다.

2. Dijkstra Algorithm [ 인접 노드]

이번에도 geeks for geeks 사이트 코드를 참고하여 이해하였다.

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm

 

기본적인 개념에 대한 부분은 아래 블로그를 보면서 이해하였다.

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

Dijkstra 알고리즘의 궁극적인 목적은 모든 vertex를 방문하면서, cost를 완성시키는 것이다.

이 알고리즘은 시작 vertex를 알려줘야 하는데, 위 코드에서는 0번으로 보내주었다.

 

우선 cost의 value가 모두 큰 값(sys.maxsize)으로 저장된 상태에서, 0번 노드에서의 길이 있는 지 유무와 방문 유무를 확인한다.

지금은 첫 loop이므로 당연히, 0번 노드가 갈 수 있는 길들은 not visited 상태일 것이다.

 

따라서, cost[u] > cost[x] + self.g[x][u] 로 이전 비용이 현재 노드를 거쳐서 해당 노드를 방문 하는 것 보다 크다면, 더 작은 비용으로 갈 수 있는 값을 추가해 준다.

 

이를 vertex 번 반복을 통해 모든 노드의 방문을 완료시킨다.

이를 통해서 0번 vertex에서 다른 vertex까지의 최단 경로를 구할 수 있다.

 

2'. Dijkstra Algorithm [힙]

geeks for geeks 코드!

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/

Dijkstra's Shortest Path Algorithm using priority_queue of STL - GeeksforGeeks

 

Dijkstra 알고리즘을 O(nlogn)의 시간 복잡도로도 해결할 수 있다.

바로, heapq를 이용하는 것이다.

import heapq
import sys

class Dij:
    def __init__(self, vertex, edge):
        self.vertex = vertex
        self.edge = edge
        self.g = [[] for _ in range(vertex + 1)]

        for _ in range(edge):
            u, v, w = map(int, input().split())
            self.g[u].append([v, w])

    def min_cost(self, start, end):
        costs = [sys.maxsize] * (self.vertex + 1)
        costs[start] = 0

        hq = []
        heapq.heappush(hq, (0, start))

        while hq:
            cur_w, u = heapq.heappop(hq)

            if cur_w > costs[u]:
                continue

            for v, w in self.g[u]:
                cost = costs[u] + w
                if costs[v] > cost:
                    costs[v] = cost
                    heapq.heappush(hq, (cost, v))

        return costs[end]


if __name__ == "__main__":
    n = int(input())
    m = int(input())
    dij = Dij(n, m)
    start, end = map(int, input().split())
    print(dij.min_cost(start, end))

cur_w, u로 pop을 해준다.

해당 start에서 u까지 cur_w만큼의 비용이 소요된다는 뜻이다.

하지만 heapq에 넣고 나서도, costs[u] 가 수정될 수도 있으니, costs[u] < cur_w 인지 확인한 후, 추후에 수정된 값이 더 작아졌다면 해당 과정을 continue를 통해 생략한다.

 

u의 인접 노드 v로 갈 수 있는 가중치 w에 대한 계산을 통해 costs[v] 보다 cost[u] + w(u에서 v로 이동하는 가중치) 가 작다면, u vertex를 거쳐서 가는 것이 더 저렴하므로, 해당 costs[v]를 수정해 준다.

 

이후, v로 가는 새로운 최단 경로가 발견되었으므로, v 인접 vertex 에 대해서, 다시 경로 계산을 진행해 주어야 한다.

따라서, heapq.heappush(hq, (cost, v))를 통해서 다시 최단 경로 계산을 진행하도록 한다.

 

 

geeks for geeks와 다른 코드는 

            if cur_w > costs[u]:
                continue

이 부분이다. 이를 통해서, costs[u] 가 추후에 더 짧은 가중치로 수정되었는지, 확인을 통해 continue를 해주는 부분이다.

 

마지막으로 Dijkstra 알고리즘은 greedy 알고리즘과 달리 항상 최적해를 제공한다.

greedy algorithm에 근본을 두고 있으므로 edge은 모두 양의 값을 가지고 있어야 한다. 해당 알고리즘은 네비게이션에 이용되곤 한다.

 

3. Floyd Warshall

https://www.youtube.com/watch?v=9574GHxCbKc

 

이 영상으로 전체적인 Floyd Warshall 알고리즘에 대한 흐름을 이해하였고, 

 

코드는 역시 geeks for geeks를 참고하였다.

https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

Floyd Warshall Algorithm - GeeksforGeeks

 

이 알고리즘은 특정 노드에서 특정 노드까지의 모든 최단 경로를 구하는 알고리즘이다.

따라서, O(n^3)의 큰 시간 복잡도를 지니게 된다.

Dijkstra 알고리즘과 달리 음의 값을 가중치로 지닐 수 있다. 하지만, 음의 가중치 cycle은 형성되면 안된다. -> cycle이 형성될 경우 거리가 무한대로 작아질 수 있다.

Floyd Warshall 알고리즘은 greedy 알고리즘과 달리 모든 경유지를 탐색하므로 음수 가중치가 있어도 경로가 갱신되기 때문에 가능하다.

 

 

모든 경로를 탐색하기 때문에 3중 for문을 작성하면 된다.

 

get_all_cost의 함수의 첫 2중 for문은 형성되어 있는 edge에 대한 정보를 복사해 주기 위함이다.

이후, 3중 for문이 나오는데, 이는 i에서 j로 이동할 때, k를 거쳐서 이동할 경우 더 작은 cost를 가지는 지 확인한다.

따라서 i -> j 와 i -> k -> j 까지의 거리를 비교해서 더 작은 값으로 바꾸어 준다.

 

3중 for 문에서 cost[2][2] = min(cost[2][2], cost[2][2] + cost[2][2])와 같은 경우도 등장하게 되는데, 둘 다, 0의 값을 나타내므로 괜찮다. 의미가 없는 코드 실행이 될 것이지만, 이에 대한 예외 처리를 할 경우 오히려 더 복잡도가 증가하기 때문에, 소소하게 넘겨주도록 한다.