迪杰斯特拉算法（Dijkstra算法）

 
//Dijkstra算法解最短路径问题 
#include<iostream>
using namespace std;
 
const int INF=99999;
 
int main()
{
     int dist[105][105] ;
   int book[105] ;
   int i,j,n,m,a,b,c,u,v,Min;
 
     cin>>n>>m;
 
     //开始了！！！
     for(i = 1;i <= n;i++)  //每轮循环计算的是中转点为n-1时的最小点。
          for(j = 1;j <= n;j++)
              if(i == j)  dist[i][j] = 0;
              else        dist[i][j] = INF;
 
    	for(i = 1;i <= m;i++)
              {
                    cin>>a>>b>>c;
                    dist[a][b] = c;
                    dist[b][a] = c;
              }
              
 
          for(i = 1;i<=n;i++)   //初始化标记book 
                   book[i] = 0;
                   
        for (i = 1; i <= n; i++) {
        	 book[i] = 1;
          for(i = 1;i <= n-1;i++)  //筛出当前没有访问的并且与上一点直接相连的距离最小的点。
       	 {
               Min = INF;
               for(j = 1;j <= n;j++)
               {
                     if(book[j] == 0&& dist[i][j] < Min)
                     {
                           Min = dist[i][j];
                           u = j;
                     }
               }
 
 
          book[u] = 1;
          for(v = 1;v <= n;v++) //松弛
          {
                if(dist[u][v] < INF)
                {
                      if(dist[i][v] > dist[i][u] + dist[u][v])
                           dist[i][v] = dist[i][u] + dist[u][v];
                }
          }
        }
         book[i] = 0;
		}
                   
       
        
        for(i  = 1;i <= n;i++){
        	for(j = 1; j <= n; j++) {
        		 cout<<dist[i][j]<<"\t";
			}
			cout<<endl;
		}        		           
            
    return 0;
}