最短路径Dijkstra

最短路径定义：

通俗的讲就是：在一个带权图中，A到B顶点存在一条权值最短的路径----->最短路径

关于最短路径与最小生成树的区别

关于区别来看看这个例子：

总结：最小生成树所选择的路径未必是最短的。

最短路径的算法

思考的方法也是用的贪心策略：假设现在（v源，vk）是第一条最短的路径，那么下面第二条最短路径是哪一条呢？

在假设下一条最短路径的顶点为vj，那么有两种可能（v源，vj）或者（v源,vk,vj） 。

通常情况下，下一条最短路径总是在“由已经产生的最短路径再扩充一条边”形成的最短路径得到。

证明：

由已知可知下一条最短路径必定从v源 出发，中间经过S集合（表示已经求得的最短路径的终点集合）在扩充一条边便可到达顶点vi（vi属于V-S）的各条路径中的最短者。

如果不是，那么不妨假设在路径（v源，v1，v2......,vk）上存在另一个顶点vp（vp属于V-S），使得（v源，v1，v2......,vp,vk）成为另一条终点不在S而长度比路径（v源，v1，v2......,vk）还短的路径。

因为我们按照最短路径的长度递增的次序，来逐次产生各条最短路径，因此长度比这条路径短的所有路径都已经产生，而且他们的终点一定也再S集合中，故假设不成立。

有了上面的结论之后，我们就可以开始解决最短路径问题了。

首先要引进dist[k]=min{dist[i]|vi属于V-{v源}}来记录距离值表示两个含义，即针对S集合和V-S集合

• 集合S中顶点的距离值是从顶点v0到该顶点(vk)的最短路径长度；
• 集合V-S中顶点的距离值是从顶点v0到该顶点(vk)的只包括集合S中顶点为中间顶点的最短路径长度(通俗讲:将S集合的顶点为中介点，计算vk到中介点集合的最短路径长度)。

我们的思想是：

• 开始是集合S中只有源点v源 ，然后不断的从集合T（V-S）中选取到顶点 v源 路径最短的顶点Vk并入到集合S中。
• 集合S每加入一个新的顶点Vk，都要修改顶点v源到集合T中的顶点的最短路径长度值。（很重要）
• repeat上述过程。

部分代码如下：

/*
*dist[i]表示距离值。
*path[i]记录路径的数组。
*visited[i]标记是否访问过。
*是以邻接矩阵为存储结构。
*/
 
void Dijkstra(Mgraph g,int v,int dist[],int path){
    int visited[Max];
    int min,i,j,u;
    //初始化dist
    for(i=0;i<g.n;i++){
        dist[i]=g.edges[i][j];
        visited[i]=0;
        if(g.edges[i][j]<INF){
            path[i]=v;
        }
        else{
            path[i]=-1;
        }
    }
    visited[v]=1;path[v]=-1;
    //初始化结束
 
    // 关键操作
    for(i=0;i<g.n;i++){
        min =INF;
        //选出未访问顶点，距离值最短的
 
        for(j=0;j<g.n;j++){
            if(visited[j]==0&&dist[j]<min){
                u=j;
                min = dist[j];
            }
        }
 
        visited[u]=1;
​    ​    //更新dist数组
        for(j=0;j<g.n;j++){
            if(visited[j]==0&&dist[u]+g.edges[u][j]<dist[j]){
                dist[j]=dist[u]+g.edges[u][j];
                path[j]=u;
            }
        }
    }
    //关键操作结束
}