Dijkstra

Problem:

Given a bidirectional graph of N (1 \le N \le 50000) vertices and M (N-1 \le M \le 100000) edges and the weight w_i (0 \le w_i \le 1000) of each edge, find the shortest path from node 1 to each node.

Input (file.in):

Line 1: Two integers, N and M.
Lines 2 \ldots M+1: Three integers, a, b, and t that represent the weight of the edge between nodes a and b is t.

Output (file.out):

Lines 1 \ldots N: The distance from node 1 to node i.

Solution:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
* Example Dijkstra with Priority Queue and Adjacency List
* Albert Gural
*/
 
#include <fstream>
#include <vector>
#include <queue>
 
using namespace std;
FILE *fin  = fopen("file.in",  "r");
FILE *fout = fopen("file.out", "w");
int N, M, a, b, t;   // N = nodes, M = edges, t is dist from a to b
int     dist[50005]; // distance from node 1
bool visited[50005]; // whether a node has been processed
vector<pair<int,int> > edges[50005]; // Adjacency List
vector<pair<int,int> >::iterator it;
 
int main () {
    fscanf(fin, "%d %d", &N, &M);
 
    // Initialize adjacency list with empty vectors.
    for(int i = 0; i <= N; i++) {
        vector<pair<int,int> > v;
        edges[i] = v;
    }
 
    // Initialize distances (all but node 1 are at "infinity").
    dist[1] = 0;
    for(int i = 2; i <= N; i++)
        dist[i] = 1000000000;
 
    // Fill Adjacency list with data from input.
    for(int i = 0; i < M; i++) {
        fscanf(fin, "%d %d %d", &a, &b, &t);
        edges[a].push_back(make_pair(b, t));
        edges[b].push_back(make_pair(a, t));
    }
 
    // Initialize Priority Queue with first node.
    // Priority Queue will be a collection of Pair<int, int>.
    // First element gives distance from x to node 1.
    // Second element gives x.
    priority_queue<pair<int,int>, vector<pair<int, int> >,
        greater<pair<int,int> > > q;
    q.push(make_pair(0,1));
 
    // Dijkstra
    while(!q.empty()) {
        int cur = q.top().second;   // Current Node
        int dcur = q.top().first;   // Current Node's Distance
        q.pop();                    // Remove top element.
        if(visited[cur]) continue;
        visited[cur] = true;
 
        // Look at each node adjacent to the current node.
        // If the distance to those nodes + current distance is
        // less than the current distance of those nodes, update it
        // and add it to the queue.
        for(it = edges[cur].begin(); it != edges[cur].end(); it++) {
            int nextNode = (*it).first;  // Adjacent node to cur
            int distNext = (*it).second; // Dist from adj. node to cur
            if(dist[nextNode] > dcur + distNext) {
                dist[nextNode] = dcur + distNext;
                q.push(make_pair(dist[nextNode], nextNode));
            }
        }
    }
 
    // The shortest path from node 1 to all other nodes is
    // now stored in the dist array.  Print each value of dist.
    for(int i = 1; i <= N; i++)
        fprintf(fout, "%d\n", dist[i]);
    return 0;
}