Tìm đường đi ngắn nhất sử dụng thuật toán dijkstra

Bài toán như sau:

Cho G = (V,E) là đơn đồ thị liên thông (vô hướng hoặc có hướng) có trọng số
V = {1,.., n} là tập các đỉnh , E là tập các cạnh (cung).
Cho s0 € E. Tìm đường đi ngắn nhất đi từ s0 đến các đỉnh còn lại. Giải bài toán trên bằng thuật toán Dijkstra .

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000
const int oo = 1000111000;
typedef pair<int, int> ii;

vector <ii> a[maxn];
int n, m, s;
int d[maxn];
int trace[maxn];
int aa[maxn][maxn];
int sinhtest()
{
    srand(time(NULL));
    string filein = "input.txt";
    ofstream myfile;
    myfile.open (filein);
    int n = rand()%10 +1;
    myfile << n << " ";
    int m = rand()%(n*(n-1)/2) + 1;
    myfile << m << endl;
    int s = rand()%(n) + 1;
    myfile << s << endl;
    for(int i = 1; i<= n ;i++)
        for(int j= 1; j<= n; j++) aa[i][j] = 0;
    for(int i= 1; i<= m ;i++)
    {
        int x, y , w;

        do
        {
            x = rand()%n +1;
            y = rand()%n + 1;
            w = rand()%10000 + 1;

        }while(aa[x][y] != 0 or aa[y][x] != 0);
        aa[x][y] = w;
        myfile << x << " " << y <<  " " << w << endl;
    }



    myfile.close();
}

void dijkstra(int s){
    priority_queue <ii, vector<ii>, greater<ii> > pq;

    for (int i=1; i<=n; i++) d[i] = oo;
    d[s] = 0;
    pq.push(ii(0, s));

    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 uv=a[u][i].first;
            int v = a[u][i].second;
            if (d[v]>du+uv) {
                d[v]=du+uv;
                trace[v] = u;
                pq.push(ii(d[v], v));
            }
        }
    }

}

int main(){
   // sinhtest();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n >> m>> s;
    while (m--){
        int p, q, w;
        cin >> p >> q >> w;
        a[p].push_back(ii(w, q));
        a[q].push_back(ii(w, p));
    }

    dijkstra(s);

    for (int i= 1; i<= n; i++)
    {
        if (d[i] == oo)
        {
            cout << "Khong co duong den" << endl;
            continue;
        }
        cout << i << ":\t\t" << d[i] << endl;
        int vt = i;
        stack <int> trace_save;
        trace_save.push(vt);
        while( vt != s) {
            vt = trace[vt];
            trace_save.push(vt);
        }
        while(1)
        {
             cout << trace_save.top();
            trace_save.pop();
            if (!trace_save.empty()) cout << " -> ";
            else break;
        }

        cout << "\n--------------------------\n";
    }
}

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.