最短路径问题（Dijkstra算法）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x6fffffff
using namespace std;
const int maxn = 10010;
int map[maxn][maxn];
int dist[maxn];
int pre[maxn];
int s;
int n;
bool p[maxn];
void Dijkstra(){
    int i,j,k;
    int min;
    for(i = 1; i <= n; i++){
        p[i] = false;
        if(i != s ){
            dist[i] = map[s][i];
            pre[i] = s;
        }
    }
    dist[s] = 0;
    p[s] = true;
    for(i = 1; i <= n-1; i++){
        min = INF;
        k = 0;
        for(j = 1; j <= n; j++){
            if(!p[j] && dist[j] < min){
                min = dist[j];
                k = j;//在Vb中取一点K
            }
        }
        if(k == 0){ return ;}
        p[k] = true;
        printf("dist[%d] = %dn",k,dist[k]);
        for(j = 1; j <= n; j++){
            if(!p[j] && map[k][j] != INF &&dist[j] > dist[k] +map[k][j]){
                dist[j] = dist[k] + map[k][j];
                pre[j] = k;
             }
        }
    }
}

int work(){
    int tal = 0;
    for(int i = 1; i <= n; i++){
        if(p[i] == true){
            tal += dist[i];
        }
    }
    return tal;
}
void init(){
    memset(pre,sizeof(pre));
    memset(dist,sizeof(dist));
    memset(p,false,sizeof(p));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            map[i][j] = 0;
        }
    }
}

int main()
{
    while(scanf("%d",&n) != EOF){
        init();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d",&map[i][j]);
                if(map[i][j] == 0){ map[i][j] = INF; }
            }
        }
        printf("please input the source :n");
        scanf("%d",&s);
        Dijkstra();
        int res = work();
        printf("The total length is %dn",res);
    }
    return 0;
}
/***************
测试数据：
6
0 2 1 4 0 0
2 0 3 0 0 0
1 3 0 2 4 6
4 0 2 0 0 0
0 0 4 0 0 1
0 0 6 0 1 0
1
************/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!