Dijkstra算法是求最短路径的一种很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
算法的基本思路：
1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
之前做了一道算法题用到过dijkstra算法，具体题意忘了，这里贴一下源代码作为dijkstra算法的示例代码：
#include<iostream>
#include<cstring>
using namespace std;
const int MIN=1000000;
int flag[5];
int a[5][5];
int dis[5];
int main()
{
memset(flag,0,sizeof(flag));
memset(a,MIN,sizeof(a)); //初始化矩阵
int dian,bian;
int u,v1,w1;
cin>>dian>>bian; //输入点和边的数量
for(int i=0;i<bian;i++)
{
cin>>u>>v1>>w1;
a[u][v1]=w1; //填充邻接矩阵
}
for(int i=0;i<dian;i++)
{
dis[i]=a[0][i]; //dis[i]表示从起点到顶点i的距离
}
flag[0]=1; //标记顶点是否已加入集合
dis[0]=0;
int v=0,w;
for(int i=0;i<dian;i++)
{
int min=MIN;
for(w=0;w<dian;w++)
if(!flag[w]&&dis[w]<min) //找到不在集合中并且离起点距离最短的顶点
{
v=w; //记录顶点
min=dis[w];
}
flag[v]=1;
for(w=0;w<dian;w++) //更新选中的顶点到未选中顶点集合中所有顶点的距离
if(!flag[w])
if(min+a[v][w]<dis[w]) //通过中间顶点来更新
dis[w]=min+a[v][w];
}
for(int i=0;i<5;i++)
cout<<dis[i]<<endl;
return 0;
}