最短路径问题—ijkstra算法）

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define INF 0x6fffffffusing 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] = %d\n", 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, 0, sizeof(pre));    memset(dist, 0, 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 %d\n", res);    }    return 0;}/***************测试数据：60 2 1 4 0 02 0 3 0 0 01 3 0 2 4 64 0 2 0 0 00 0 4 0 0 10 0 6 0 1 01************/

3楼leihengxin昨天 22:36

顶一下。

2楼wangwenhao00昨天 22:20

谢谢，你QQ多少呀？多交流交流呗。

1楼djkkcc昨天 22:18

顶一下,希望结交.