由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V1，首先选择其直接相邻的顶点中长度最短的顶点Vi的距离为dist[i]，那么可知V1到i的最短距离就是dist[i]，因为从经过其他点中转一定会延长路径。所以dist[i]不再是估计值而是确定值，V1到i的最短距离就是dist[i]，那么当前已知可得从V1到达V2...n(except i) 顶点的最短距离估计值为dist[2...n]=min{dist[2...n],dist[i]+matrix[i][2...n]}。

所以得到了一个更新的dist数组。除了dist[i]以外，找到其中的最小值dist[i‘]，所以可断言，源点V1到i‘的最短距离就是dist[i‘]，因为除了dist[i]以外比它小外，其他dist[x]都比它大，所以以其他点作为中转到达i‘一定会延长路径，只可能以i为中转。

所以“dist[2...n]=min{dist[2...n],dist[i]+matrix[i][2...n]}。”式子的意义就是考虑以i点为中转经过2...n其他各点。

这样以来已经有两个估计值变成确定值了（i,i‘），按同样的思路确定i‘‘，直至算法结束。

思路总结：

假设存在G=<V,E>，源顶点为V1，确定点集U={V1},估计值dist[i]记录V1到i的可能最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。

dist[i]初始化是V1到各点的直接距离（不经任何点中转）

1.从dist中dist[i]值最小的顶点i，将i加入到U中；

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.直到U=V，停止。

练习：

#include<cstdio>
#include<iostream>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
int n,m;
int a,b,c;
int dis[105];
int mapp[105][105];
bool book[105];
void ini()
{
    memset(dis,0,sizeof(dis));
    memset(mapp,0,sizeof(mapp));
    memset(book,false,sizeof(book));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        mapp[i][j]=inf;
    }

    while(m--){
        cin>>a>>b>>c;
        mapp[a][b]=c;
        mapp[b][a]=c;
        if(a==1) dis[b]=c;
        if(b==1) dis[a]=c;

    }
    for(int i=1;i<=n;i++) dis[i]=mapp[1][i]; //1点到所有点的初始路径
}
void Dijkstra()
{
    for(int j=1;j<=n;j++){
        int minn=inf;
        int cur;
        for(int i=1;i<=n;i++){
            if(dis[i]<minn&&!book[i]) {minn=dis[i];cur=i; }
        }
        book[cur]=1;
        for(int i=1;i<=n;i++){
            if(!book[i]&&mapp[cur][i]!=inf&&dis[i]>dis[cur]+mapp[cur][i] )
                dis[i]=dis[cur]+mapp[cur][i];
        }
    }
}
int main()
{
    while(cin>>n>>m&&n)
    {
        ini();
        Dijkstra();
        cout<<dis[n]<<endl;
    }
    return 0;
}