d[i]——从源点到 i点的最短距离

f[i]——i的父节点

p[i]——标记i的最短路是否确定：0 不确定；1 确定

d[]置无穷大

d[s]=0;

for (k=1;k<=n;k++){

    min=∞;

    for (j=1;j<=n;j++)

        if (p[j]==0 && d[j]<min){

            min=d[j]; i=j;

        }

    if (min=∞) break;

   

    p=1;

    for (j=1;j<=n;j++)

        if (p[j]==0 && g[i][j]>0 && d[i]+s[i][j]<d[j]){

            d[j]=d[i]+g[i][j];

            f[j]=i;

        }

}

 

08.8.17(在学校学dijkstra)

#include<stdio.h>

    long i,j,k,m,n;

    long dist[101],vis[101];

    long w[101][101];

    long s,t;

void init(){

    long x,y,z;

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

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

        for(j=1;j<=n;j++)

            w[i][j]=100000000;

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

        dist[i]=100000000;    

        vis[i]=1;

     }

     for(i=1;i<=m;i++){

         scanf("%ld%ld%ld",&x,&y,&z);                 

         w[x][y]=z;w[y][x]=z;

     }

     scanf("%ld%ld",&s,&t);         

}

void work(){

    long min;

    dist[s]=0;

    do{

        min=100000000;

        k=0;

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

          if(vis[i]==1 && dist[i]<min){

              min=dist[i];

              k=i;            

        }

        if(k==0)break;

        vis[k]=0;

       

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

            if(dist[i]>(min+w[k][i]))

                dist[i]=min+w[k][i];

    }while(true);   

}

void out(){

    printf("%ld",dist[t]);

}

main(){

    freopen("dijkstra.in","r",stdin);

    freopen("dijkstra.out","w",stdout);

        init();

        work();

        out();                            

    return 0;

}