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

다익스트라 알고리즘

다익스트라(dijkstra) 알고리즘은 그래프에서 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

다익스트라 알고리즘 과정

예를들어 아래와 같은 경로의 그래프가 있다고 하자.

다익스트라 알고리즘 예제

위 그림은 아래 처럼 표현 할 수 있다. 그래프를 보면서 이해하면 더 쉽다.

6 11 <- 노드 개수, 간선 개수
1 <- 출발노드
1 2 2 <- 1번과 2번 노드가 연결되어있고 2만큼의 비용이 듬
1 3 5 <- 1번과 3번 노드가 연결되어있고 5만큼의 비용이 듬
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

우선순위 큐를 이용한 다익스트라 알고리즘 파이썬 코드

시간복잡도 O(NlogN)

 

import heapq
import sys
INF = int(1e9)


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


input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

print(dijkstra_pq(graph, start))

오늘 푼 문제

https://geonoo.tistory.com/134

[파이썬] 미래 도시 - 이코테

https://geonoo.tistory.com/135

[파이썬] 743. Network Delay Time - 리트코드

https://geonoo.tistory.com/136

[파이썬] 787. Cheapest Flights Within K Stops - 리트코드

회고

오늘은 미래도시 라는 코딩테스트 문제로 발표를 진행하게 되었다.

하기전까지는 꽤나 떨렸는데 하고나니 개운해진것도 있고 깔끔하게 설명했다고 하니 기분이 참 좋았다.

그리고 자바공부를 다시 시작했다. 전에 프로그래머스 자바 초급 강의는 다 봤었고, 지금은 중급을 좀 봐야겠다.

이번주 금요일부터 주특기 공부가 시작된다. 미리 좀 준비해놔야겠다.