최단경로

최단경로

최단경로( ex. A에서 B로 가는 최단 경로)

• 그래프로 표현 각 지점은 노드, 도로는 간선.
• 다익스트라, 플로이드-워셜

---

다익스트라 알고리즘

---

INF = int(1e9)


def dijkstra_naive(graph, start):
    def get_smallest_node():
        min_value = INF
        idx = 0
        for i in range(1, N):
            if dist[i] < min_value and not visited[i]:
                min_value = dist[i]
                idx = i
        return idx

    N = len(graph)
    visited = [False] * N
    dist = [INF] * N

    visited[start] = True
    dist[start] = 0

    for adj, d in graph[start]:
        dist[adj] = d

    # N개의 노드 중 첫 노드는 이미 방문했으므로,
    # N-1번 수행하면 된다.
    for _ in range(N - 1):
        # 가장 가깝고 방문 안한 녀석을 고르고,
        cur = get_smallest_node()
        visited[cur] = True
        # 최단거리를 비교, 수정한다.
        for adj, d in graph[cur]:
            cost = dist[cur] + d
            if cost < dist[adj]:
                dist[adj] = cost

    return dist

import heapq


def dijkstra_pq(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    # 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
    # 첫 번째 방문 누적 비용은 0이다.
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        # 누적 비용이 가장 작은 녀석을 꺼낸다.
        acc, cur = heapq.heappop(q)

        # 이미 답이 될 가망이 없다.
        if dist[cur] < acc:
            continue

        # 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    return dist

---

시간복잡도

• Naive : 이중 for문 -> O(V^2)
• Priority Queue : for문 하나를 우선순위큐로 구현 -> O(ElogV)

---

• 다익스트라 : 출발점을 정했을 때 다른 노드에 이르는 최단거리.
• 플로이드-워셜 : 모든 지점에서 다른 모든 지점 까지의 최단거리.
  • 플로이드-워셜은 노드의 개수가 N개일때, 알고리즘상으로 N번의 단계를 수행하며,
    단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다.
    따라서 시간복잡도는 O(N^3)이다.
  • 플로이드-워셜은 다익스트라와 다르게 2차원 리스트에 최단거리 정보를 저장한다는 특징이있다.(2차원 리스트를 처리하기때문에 O(N^2)의 시간이 소요)