是一种贪心的单源最短路径算法（可证明）。
注意点：
1. 图的链式存储（vector数组方式）。
2. 循环n次。可分为两大步骤：加入新的节点后更新最短距离、寻找下一个节点（要有最短距离）并加入集合。
时间复杂度：
//Dijstra算法
#include<cstdio>
#include<vector>
using namespace std;
struct E{
int next; //代表直接相邻的顶点
int c; //代表该边的权值
};
vector<E> edge[2001]; //邻接链表
bool mark[2001]; //标注为True时表示该结点最短路径长度得到,已加入集合K
int Dis[2001]; //当标注为True时是已得的最短路径长度,
//否则是从1出发,经过已知的最短路径达到K中的某节点,再经过一条边到达i结点的路径中的最短距离
int main(void)
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) //路口数、道路数
{
//if(n==0&&m==0) break;
for(int i=1;i<=n;i++) edge[i].clear(); //初始化邻接链表
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
E tmp;
tmp.c = c;
tmp.next = a;
edge[b].push_back(tmp); //将邻接信息加入邻接链表
tmp.next = b;
edge[a].push_back(tmp); //再次加入,因为是无向图
}
for(int i=1;i<=n;i++)//因为结点从1开始
{
Dis[i]=-1; //所有结点不可达
mark[i]=false; //所以结点不属于K
}
Dis[1]=0; //得到最近的结点为1,长度是0
mark[1]=true; //将结点1加入K
int newP = 1; //集合K新加入的结点是1
for(int k=1;k<n;k++) //循环n-1次,按照最短路径递增确定其它n-1个结点的最短路径长度
{
for(int j=0;j<edge[newP].size();j++) //遍历新加入结点的直接相邻的边
{
int t = edge[newP][j].next; //直接相邻的边的另一端
int c = edge[newP][j].c; //直接相邻的边的权重
if(mark[t]==true) continue; //另一端结点如果已经在集合K了,跳过
if(Dis[t]==-1||Dis[t]>Dis[newP]+c) //如果该结点尚不可达,或者该结点t从新加入的结点NewP经过该边到达的路径更短
{
Dis[t] = Dis[newP]+c; //更新最短距离信息
}
}
int min =123123123;//初始化大整数
for(int j=1;j<=n;j++) //遍历所有的结点
{
if(mark[j]==true) continue; //结点属于K则跳过
if(Dis[j]==-1) continue; //若该结点仍然不可达,也跳过
if(Dis[j]<min) //若该结点经由结点至集合K中的某点在经过一条边到达的距离小于当前最小值
{
min = Dis[j]; //更新其为最小值
newP = j; //新加入的结点暂定为这个点
}
}
mark[newP] = true; //确定为新加入结点
}
printf("%d\n",Dis[n]);
}
return 0;
}
2019/04/14 第一次错误更正：程序错误（更新的是新加入结点邻接边的另一端结点）。