是一種貪心的單源最短路徑算法（可證明）。
注意點：
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 第一次錯誤更正：程式錯誤（更新的是新加入結點鄰接邊的另一端結點）。