图论——最短路——Dijkstra算法

 1 int a[3010][3010]/*图*/,d[3010],n,m;
 2 bool v[3010];//是否被访问
 3 void dijkstra(int v0)//源点
 4 {
 5     memset(d,0x3f3f3f3f,sizeof(d));//距离
 6     memset(v,0,sizeof(v));//初始化都未访问
 7     d[v0]=0;
 8     for(int i=1;i<n;i++)//重复n-1次 
 9     {
10         int x=0;
11         //找到未标记的dist最小的节点
12         for(int j=1;j<=n;j++)
13             if(!v[j]&&(x==0||d[j]<d[x]))//j为访问或dist[j]<dist[x]; 
14                 x=j;
15         v[x]=1;
16         //用x更新其他点 
17         for(int y=1;y<=n;y++)
18             d[y]=min(d[y],d[x]+a[x][y]/*x到y的边权值*/); 
19     }
20 }