자료구조/알고리즘 - 최단경로 (2)

플로이드 워셜(Floyd-Warshall) 알고리즘이란?

모든 최단 경로를 구하는 알고리즘

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

파이썬 코드

INF = int(1e9)


def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

시간복잡도 O(V^3)

오늘 푼 문제

https://geonoo.tistory.com/138

https://geonoo.tistory.com/139

https://geonoo.tistory.com/140

회고

다익스트라 알고리즘은 출발지 부터 떨어진 다른 노드들의 최단거리만 구할 수 있고, 시간복잡도가 O(NlogN) 이다.

플로이드 워셜 알고리즘은 모든 노드들 사이의 최단거리를 구할 수 있어서 여러 최단경로를 계산해야 할 때 사용하면 좋다.
단, 시간 복잡도가 O(N^3)이기 때문에 노드의 개수와 간서의 개수가 많이지면 효율성이 떨어질 수 있다.

아침부터 꽤나 피곤했다. 평소에 이 정도 까지는 아니었는데 오늘은 더 심했던 것 같다.
피곤이 누적되서 그런지 졸음도 계속오고 정신이 멍해진다...

집중력이 떨어지니까 문제도 잘 안풀리고 괜히 예민해지는것 같다.

결론 자바 람다식만 공부하고 일찍 자야겠다.