Dijkstra

Code Begin

#include "stdafx.h"
#include <stdio.h>

#define LEN 210
int max=99999999;
int map[LEN][LEN];
int dis[LEN];
int mark[LEN];

void Dijkstra(int n,int start)
{
    int i,j,min,pos;
    for(i=1;i<=n;i++){
        mark[i]=0;
        dis[i]=map[start][i];
    }

    mark[start]=1;//标记
    dis[start]=0;

    for(i=1;i<=n;i++){
        min=max;
        for(j=1;j<=n;j++){
            if(mark[j]==0 && dis[j]<min){
                min=dis[j];
                pos=j;//标记
            }
        }

        if(min==max)//已经不能通了
            break;

        mark[pos]=1;
        for(j=1;j<=n;j++){
            if(mark[j]==0 && dis[j]>dis[pos]+map[pos][j]){
               dis[j]=dis[pos]+map[pos][j];//这步跟prim算法有点不同
            }
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
   int i,j,n,line;
   int t1,t2,t3;
   if(NULL==freopen("Dijkstrai.txt","r", stdin)){
      printf("open file failed\n");
      return -1;
   }
   freopen("Dijkstrao.txt","w",stdout);
   setbuf(stdout,NULL);
   scanf("%d %d",&n,&line);//顶点数和边数
   for(i=0;i<LEN;i++){
      for(j=0;j<LEN;j++){
         if(i==j)
            map[i][j]=0;
         else
            map[i][j]=max;
      }
   }
   for(i=0;i<line;i++){
      scanf("%d %d %d",&t1,&t2,&t3); //输入各边的权值
      // 判断重边的 保存较小的值
      if(map[t1][t2]>t3){
          map[t1][t2]=t3;
      }
   }

    Dijkstra(n,1);

    printf("%d\n",dis[n]);
    return 0;
}

/* in
5 7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
out
60
*/

Code End