dijkstra算法演示

dijkstra算法演示精髓

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define loop(i,n) for(int i=0;i<(n);i++)
#define loop2(i,n) for(int i=1;i<=(n);i++)

const int maxn=10;
int inf=99999999;
int e[maxn][maxn],dis[maxn],book[maxn];
int n,m;

void dijkstra(void)
{ //找到离1号顶点最近的点
  int u,v;  
  int xmin;
  loop2(i,n-1)
  { 
    xmin=inf;
    loop2(j,n)
    {
      if(book[j]==0 && dis[j]<xmin)
      {
        xmin=dis[j];
        u=j;
      }
    }
    book[u]=1;
    loop2(v,n)  //松驰
    {
      if(e[u][v]<inf)
        if(dis[v]>dis[u]+e[u][v])
          dis[v]=dis[u]+e[u][v];
    }
  }
}

void test()
{   
  freopen("dijkstra.in","r",stdin);  
  //freopen("dijkstra.out","w",stdout); 
  cin>>n>>m;
  cout<<n<<" "<<m<<endl;
  loop2(i,n)
    loop2(j,m)
      if(i==j)e[i][j]=0;
      else e[i][j]=inf;
  int t1,t2,t3;
  loop2(i,m)
  {
    cin>>t1>>t2>>t3;
    e[t1][t2]=t3;    
  }
  loop2(i,n)
    dis[i]=e[1][i];

  book[1]=1;
  dijkstra();

  loop2(i,n)
    cout<<dis[i]<<" ";
  cout<<endl;
}

int main () 
{        
    test();        
    return 0;
}

test data:

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4