Dijkstra最短路径算法[贪心]

2021-10-21 10:50:40

Dijkstra算法的标记和结构与prim算法的用法十分相似。它们两者都会从余下顶点的优先队列中选择下一个顶点来构造一颗扩展树。但千万不要把它们混淆了。它们解决的是不同的问题，因此，所操作的优先级也是以不同的方式计算的：Dijkstra算法比较路径的长度，因此必须把边的权重相加，而prim算法则直接比较给定的权重。

源最短路径问题
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法)。这里介绍另外一个更常见的算法Dijkstra算法。

Dijkstra算法和最小生成树Prim算法最小生成树算法非常类似，大家可以先熟悉下个算法。两个算法都是基于贪心算法。虽然Dijkstra算法相对来说比Bellman-Ford 算法更快，但是不适用于有负权值边的图，贪心算法决定了它的目光短浅。而Bellman-Ford 算法从全局考虑，可以检测到有负权值的回路。

这里模仿MST(Minimum Spanning Tree)的Prim算法，我们创建一个SPT(最短路径树)，最初只包含源点。我们维护两个集合，一组已经包含在SPT(最短路径树)中的顶点S集合,另一组是未包含在SPT内的顶点T集合。每次从T集合中选择到S集合路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。

举例说明，如下图所示的图：

S集合最初为空，然后选取源点0，S集合为 {0}，源点到其它所有点的距离为 {0, 4, INF, INF, INF, INF, 8, INF} 。图中蓝色表示 SPT，迭代的过程如下

最终得到 SPT(最短路径树) 如下：

算法C++实现：

我们使用Boolean 数组sptSet[] (也有习惯用visit[]命名，表示是否访问过)，来表示顶点是否为有SPT中。sptSet[v]=true,说明顶点v在SPT中。 dist[] 用来存储源点到其它所有点的最短路径。

#include<iostream>
#include<stdio.h>
#include<limits.h>
using namespace std;

const int V=9;
//从未包含在SPT的集合T中，选取一个到S集合的最短距离的顶点
int getMinIndex(int dist[V],bool sptSet[V])
{
    int min=INT_MAX,min_index;
    for(int v=0;v<V;v++)
    {
        if(!sptSet[v]&&dist[v]<min)
            min=dist[v],min_index=v;
    }
     return min_index;
}

//打印结果

void  printSolution(int dist[],int n)
{
    printf("Vertex Distance from Source\n");
    for(int i=0;i<V;i++)
        printf("%d\t\t %d\n",i,dist[i]);
}

//source 代表顶点
void dijkstra(int graph[V][V],int source)
{
    int dist[V];// 存储结果，从源点到 i的距离
    bool sptSet[V]; // sptSet[i]=true 如果顶点i包含在SPT中

    // 初始化. 0代表不可达
    for(int i=0;i<V;i++)
    {
        dist[i]=(graph[source][i]==0)?INT_MAX:graph[source][i];
        sptSet[i]=false;
    }
     // 源点，距离总是为0. 并加入SPT
    dist[source]=0;
    sptSet[source]=true;
    
    // 迭代V-1次，因此不用计算源点了，还剩下V-1个需要计算的顶点。
    for(int count=0;count<V-1;count++)
    {
     // u，是T集合中，到S集合距离最小的点,u开始在T集合中，然后加入到S集合
        int u=getMinIndex(dist,sptSet);
        // 加入SPT中
        sptSet[u]=true;
        for(int v=0;v<V;v++)
        {
        //满足以下4个条件
        //1. 点v还没有加入到spt中
        //2. 点u和v之间可达
        //3. 点u是可达的，距离不是无穷
        //4. 经过点u之后的距离小于直接到达点v的距离
            if(!sptSet[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]<dist[v])
                dist[v]=dist[u]+graph[u][v];
        }
    }
    printSolution(dist,V);
}

int main()
{
    int graph[V][V]={ { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                    { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                    {0, 8, 0, 7, 0, 4, 0, 0, 2 },
                    { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                    { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                    { 0, 0, 4, 0, 10, 0, 2, 0, 0 },
                    { 0, 0, 0, 14, 0, 2, 0, 1, 6 },
                    { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                    { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
                    };

    dijkstra(graph, 0);

    return 0;
}

运行结果如下：输出源点0到其它各个顶点的最短距离：

码农公寓

相关文章