다익스트라 알고리즘 예시 코드 [C++, Python]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 987654321;
int d[20005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, E, u, v, w;
    cin >> V >> E;

    for (int i = 1; i < V+1; i++) { // 전체 정점 거리 무한대 초기화
        d[i] = INF;
    }

    int start;
    cin >> start;

    vector<pair<int, int>> adj[20005];

    for (int i = 0; i < E; i++) { // 인접 리스트
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    // (정점까지의 거리, 정점 번호)를 저장하는 최소 힙을 선언한다.
    d[start] = 0; // 시작 정점까지의 거리는 0이다.
    pq.push(make_pair(d[start], start)); // 시작 거리 0 최소화후 최소힙 삽입


    while(!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        if (d[cur.second] != cur.first) continue;
        for (int i = 0; i < adj[cur.second].size(); i++) {
            pair<int, int> next = adj[cur.second][i];
            if (d[next.second] <= d[cur.second] + next.first) continue;
            d[next.second] = d[cur.second] + next.first;
            pq.push(make_pair(d[next.second], next.second));
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/1753

1753번: 최단경로

이 문제의 정답이기도 하다.

 

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]  # 시작점과 시작 거리
        dist = collections.defaultdict(int)
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:  # 거리 저장이 안되어있으면
                dist[node] = time  # 거리 저장
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

이 문제의 정답이기도 하다.

 

 

---

출처

https://blog.encrypted.gg/941?category=773649 

[실전 알고리즘] 0x09강 - BFS

 

https://search.shopping.naver.com/book/catalog/32456486633?cat_id=50010920&frm=PBOKMOD&query=%ED%8C%8C%EC%9D%B4%EC%8D%AC+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+%EC%9D%B8%ED%84%B0%EB%B7%B0&NaPm=ct%3Dl78vgtt4%7Cci%3Df701ad06257574c041af4ed5be5c108b6047f8ac%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3Da3fb28618a3308e23e626cf38260466b81380bd4 

파이썬 알고리즘 인터뷰 : 네이버 도서