dijkstra.cpp

Dijkstra - Tìm đường đi ngắn nhất trên đồ thị

Mục đích : Từ một đỉnh S, ta muốn biết độ dài đường đi ngắn nhất từ S đến tất cả các đỉnh còn lại (trong đồ thị có hướng hoặc vô hướng)

Độ phức tạp : O (n log n)

dijkstra.cpp

#include <stdio.h>

#include <vector>

#include <queue>

using namespace std;

const int oo = 1000111000;

typedef pair<int, int> ii;

vector<ii> a[2309];

int n, m;

int d[2309];

void dijkstra() {

    priority_queue<ii, vector<ii>, greater<ii>> pq;

    for (int i = 1; i <= n; i++)

        d[i] = oo;

    d[1] = 0;

    pq.push(ii(0, 1));

    while (pq.size()) {

        int u = pq.top().second;

        int du = pq.top().first;

        pq.pop();

        if (du != d[u])

            continue;

        for (int i = 0; i < a[u].size(); i++) {

            int v = a[u][i].second;

            int uv = a[u][i].first;

            if (d[v] > du + uv) {

                d[v] = du + uv;

                pq.push(ii(d[v], v));

            }

        }

    }

}

int main() {

    int p, q, m, w;

    scanf("%d%d", &n, &m);

    while (m--) {

        scanf("%d%d%d", &p, &q, &w);

        a[p].push_back(ii(w, q));

        a[q].push_back(ii(w, p));

    }

    dijkstra();

    for (int i = 1; i <= n; i++)

        printf("d( 1 -> %d ) = %d\n", i, d[i]);

}

Sample Input

5 5

1 2 10

1 3 10

2 4 20

3 4 25

1 4 33

Sample Output

d( 1->1 ) = 0

d( 1->2 ) = 10

d( 1->3 ) = 10

d( 1->4 ) = 30

d( 1->5 ) = 1000111000