Dijkstra 算法去单源最短路径

//Dijkstra算法只能处理正边权问题#include <iostream>#include<cstdio>#include<cstring>#define MAX 100#define VALUE 0xffffffusing namespace std;int g[MAX][MAX];int d[MAX];//某一个点到所有点的最短距离bool used[MAX];//已经被使用的标记int v,e;void createGraph(){    int i;    int start,end,weight;    memset(g,0,sizeof(g));    scanf("%d%d",&v,&e);    for(i=0;i<e;i++)    {        scanf("%d%d%d",&start,&end,&weight);        g[start][end]=weight;        g[end][start]=weight;    }}/*从某一个点到任意一点的最短距离*/void Dijkstra(int s){    for(int i=1;i<=v;i++)    {        d[i]=VALUE;        used[i]=false;    }    d[s]=0;    while(true)    {        int t=-1;int u;        //从尚未使用的顶点中找出距离最短的        for(u=1;u<=v;u++)        {            //遍历每个点，如果该点没被使用过，并且（v==-1 或者s到u的距离小于s到t的距离（找出与s相连的权值最小的边对应的点t））            if(!used[u] && (t==-1 || d[u]<d[t]))                t=u;        }        if(t==-1)            break;        used[t]=true;        for(u=1;u<=v;u++)        {//如果s到u的最短距离大于s到t的最短距离加上t到u的权值（t到u有边），那么更新s点到任意一点的距离            if(d[u]>d[t]+g[t][u] && g[t][u]!=0)d[u]=d[t]+g[t][u];        }    }    for(int u=1;u<=v;u++)    {        printf("%d  ",d[u]);    }}int main(){    createGraph();    Dijkstra(1);    return 0;}/*5 81 2 22 3 33 4 24 5 31 3 51 4 12 4 72 5 3*/