[구름 IDE] 다익스트라 알고리즘(Dijkstra's Algorithm)(★4)

 

 

문제

소스코드

#include<iostream>
#include<queue>
#include<vector>
 
constexpr int INF = 10000000;
 
class Node {
private:
public:
    Node(int node, int weight) :node_(node), weight_(weight) {}
    int node_;
    int weight_;
    constexpr bool operator<(const Node& _Right) const {
        return weight_ > _Right.weight_;
    }
};
 
std::vector <std::vector<Node>> g_nodes;
std::vector<int> g_weight;
 
void Dijkstra(int started) {
    
    std::priority_queue<Node> queue;
    queue.emplace(Node{started,0});
    g_weight[started] = 0;
 
    while (queue.empty() == false) {
 
        Node top_node = queue.top();
        int node = top_node.node_;
        int node_weight = top_node.weight_;
        queue.pop();
 
        //해당 노드와 연결된 노드들을 본다.
        for (const auto& nodes : g_nodes[node]) {
 
            int around_node = nodes.node_;
            int around_weight = nodes.weight_;
 
            int weight = around_weight + node_weight;
            
            if (weight < g_weight[around_node]) {
                g_weight[around_node] = weight;
                queue.emplace(Node{ around_node,weight });
            }
        }
    }
 
}
 
 
int main() {
    int N, E;
    std::cin >> N >> E;
 
    g_weight.assign(N + 1, INF);
    g_nodes.assign(N + 1, std::vector<Node>(N + 1, Node(0, 0)));
 
    for (int i = 0; i < E; ++i) {
        int start_node, end_node, weight;
        std::cin >> start_node >> end_node >> weight;
        g_nodes[start_node].emplace_back(Node{ end_node,weight });
        g_nodes[end_node].emplace_back(Node{ start_node,weight });
    }
    int started;
    std::cin >> started;
 
    Dijkstra(started);
 
    for(int i=1;i<=N;++i){
        std::cout << i << ": " << g_weight[i] << "\n";
    }
}

 

 

 

후기

이 문제를 해결하기 위한 키워드는 다익스트라이다.

다익스트라는 최단경로를 알 수 있는 알고리즘 중 하나이며 자세한 다익스트라에 관한 설명은 관련 글에 링크를 해놨다.

 

 

다익스트라 문제는 안 풀면 잊어먹을 거 같아서 주기적으로 풀고 있다.

 

출처 및 레퍼런스

문제 링크:https://level.goorm.io/exam/43211/다익스트라-알고리즘-dijkstra-s-algorithm/quiz/1

 

관련 글

[자료구조 알고리즘/탐색 알고리즘] - 다익스트라 알고리즘(Dijkstra algorithm)

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타알고 시즌2 학교 지도 만들기(★3)

[온라인 코딩/탐색(Search)] - [백준] 1753번 최단경로