最短路径 - 迪杰斯特拉(Dijkstra)算法详解

发布于 / 数据结构与算法 / Comments Off on 最短路径 - 迪杰斯特拉(Dijkstra)算法详解

0x00、梗概

迪杰斯特拉(Dijkstra)算法是著名用来求最短路径的算法。被用于计算一个点到另一个点的最短路径。

其本质是贪心策略,主要思想和广度优先搜索(BFS)差不多,最大的特征是"层层遍历,直到终点"。


(Dijkstra算法发明者:艾兹格·W·迪科斯彻)

0x01、思路

Dijkstra算法是用来求图中某个顶点到另一个顶点的最短路径。这里的"最短"指代的不一定是"路程最短",而是边权累加之和最短。

使用Dijkstra算法计算时,思路如下:

  1. 指定起点s

  2. 定义两个集合:S和U,这里S用来记录已求出最短路径的途经顶点、以及相应最短路径的长度;U用来记录尚未求出最短路径的顶点、以及这个顶点到起点s的距离。

  3. 在初始时的状态:集合S中只包含起点s,集合U中包含除了起点s之外的所有顶点。

  4. 在Dijkstra执行的过程:{在U中找出路径最短的顶点 v,并将其加入到S中。接着更新U中的顶点。并以v为中介点,重新计算U中顶点到起点的距离,取最小值写入U }。接着再{从U中找出路径的顶点,加入到S中。并更新U中顶点,以及其所对应路径} 。。。。不断循环

  5. 直到遍历完全部顶点。

0x02、实现

我们举个实例帮助我们来讲解Dijkstra算法是如何实现的吧!

比如下面这个图


图中A-G表示顶点,边上的数字为边权。

我们以D为起点举例。

第一步:将起点D放入容器S,除了起点D之外的所有点放入容器U。

接着更新U容器内,各个顶点到D的距离。例如C到D距离为(C,D)=3,而F到D没有直达路线,(F,D)=INF(无穷大)

第二步:在U中,路径最小的是C,它到D的距离只有3。将C放入集合S中,同时将C从集合U中删除。

接着以C为中介点,更新U容器。B到D的距离为(B,C)+(C,D)=13,E到D的距离为(E,C)+(C,D)=8,而这个8大于数组原来的4,所以仍然取最小值4。F到D的距离为(F,C)+(C,D)=9

第三步:在U中,路径最小的是E,它到D的距离只有4。将E放入集合S中,同时将E从集合U中删除。

接着更新U容器。B到D的最短距离仍然是13,F到D的最短距离为(F,E)+(E,D)=6,G到D的最短距离为(G,E)+(E,D)=12

第四步:将最短的F放入S,并从U中删除。然后更新U

第五步:思路同上

第六步:

第七步:将A放入S,集合U为空了。遍历结束。此时集合S中就是每个点到顶点D的最短边权值(最短路径)

0x03、C语言实现

根据上面的思路先写出伪代码:

/* *
   * Dijkstra
   * G为图,d为数组,存放起点到各个点的最短路径长度,s是起点
   */
Dijkstra(G, d[], s){
    初始化操作;    //将d数组全部初始化为INF,令d[s]=0(起点到自身距离为0);
    for(循环n次){    //其中n为顶点数,循环的目的是遍历所有点
        u = 使得d[u]最小,且还没有被访问的顶点编号    //取出最小距离点
        标记u为已访问                            //防止重复遍历
        for(从u出发能到达的所有顶点v){            //枚举更新
            if(v尚未访问 && 以u为中介点,使得s到v的最短距离比已求出的d[v]更优){
                更新d[v]                      //有更优路径,则更新
            }
        }
    }
}

在编写C语言代码之前,有两点注意:

  1. 前面说的"存放已经遍历过的节点的集合" S ,可以用一个bool型的数组 visited[ ] 来实现,visited[i] = true表示第 i 个节点已被访问,为false表示第 i 个节点尚未被访问。

  2. 那个非常大的数可以使用16进制数:0x3fffffff来表示。0x3fffffff=1073741823

图的存储可以使用邻接矩阵或者邻接表,我们依次编写。

先定义最大顶点数和INF:

#define MAXN 1000
#define INF 0x3fffffff

1、邻接矩阵型

以下是邻接矩阵型的Dijkstra函数:

int n, G[MAXN][MAXN];    //n为顶点数,G为邻接矩阵
int d[MAXN];    //d数组存储起点到达各点最短路径长度
bool visited[MAXN] = {false}; //标记数组,前面说过了

/*Dijkstra算法。参数s为起点的编号*/
void Dijkstra(int s){
    //下面两行为初始化操作
    fill(d, d+MAXV, INF);    //将数组d全部赋值为很大的数
    d[s] = 0;    //起点到自己本身的距离为0
    for(int i = 0; i < n; i++){    //循环n次,n是顶点数,处理每一个点
        int u = -1, MIN = INF;    //u存放"用来找数组d中最小值的下标",MIN存放"数组d中的最小值"
        for(int j = 0; j < n; j++){   //枚举每一个点
            if(visited[j] == false)    //如果这个点没有处理过
                if(d[j] < MIN){         //并且这个点到顶点的距离比MIN小(MIN的初始值很大)
                    u = j;        //让u等于最小值的下标
                    MIN = d[j];   //MIN等于d中的最小值
                }
        }
        //如果u==-1,说明没有找到,也就是剩下的顶点与起点s不连通,我们直接终止函数
        if(u == -1) return;
        //如果找到了最小值的那个点,进行后续步骤
        visited[u] = true;    //标记这个点为已经访问过
        for(int v = 0; v < n; v++){    //枚举每一个点
            if(visited[v] == false)     //如果这个点没有处理过
                if(G[u][v] != INF)       //如果刚刚那个最小值的点与这个点之间有路可走
                    if(d[u]+G[u][v]<d[v]) //如果以最小值点为中介点,到起点的距离小于之前算的起点的距离(如果之前没算过就是INF,一定成立)
                        d[v] = d[u] + G[u][v];    //更新d[v],使得d[v]最小
        }
    }
}

以上就是邻接矩阵版的Dijkstra函数,下面我们尝试编写邻接表版。我们依然使用vector而不是链表来存储邻接表

2、邻接表型

typedef struct{
    int v, dis;    //v为边连接的目标顶点,dis为边权
} Node;

vector<Node> G[MAXN];
int n;
int d[MAXN];
bool visited[MAXN] = {false};

void Dijkstra(int s){    //s为起点
    /*前面的所有写法与邻接矩阵版写法相同*/
    //初始化操作
    fill(d, d+MAXV, INF);    //将数组d全部赋值为很大的数
    d[s] = 0;    //起点到自己本身的距离为0
    for(int i = 0; i < n; i++){    //循环n次,n是顶点数,处理每一个点
        int u = -1, MIN = INF;    //u存放"用来找数组d中最小值的下标",MIN存放"数组d中的最小值"
        for(int j = 0; j < n; j++){   //枚举每一个点
            if(visited[j] == false)    //如果这个点没有处理过
                if(d[j] < MIN){         //并且这个点到顶点的距离比MIN小(MIN的初始值很大)
                    u = j;        //让u等于最小值的下标
                    MIN = d[j];   //MIN等于d中的最小值
                }
        }
        //如果u==-1,说明没有找到,也就是剩下的顶点与起点s不连通,我们直接终止函数
        if(u == -1) return;
        //如果找到了最小值的那个点,进行后续步骤
        visited[u] = true;    //标记这个点为已经访问过
        /*仅此处的for循环与邻接矩阵版的写法不同*/
        for(int j = 0; j < G[u].size; j++){    //枚举临街表中的所有顶点
            int v = G[u][j].v;    //此处可以通过临街表直接获得顶点。不用像邻接矩阵那样枚举
            if(visited[v] == false)             //如果这个点没有被访问过
                if(d[u]+G[u][j].dis < d[v])    //并且边权和小于之前计算过的最短路径
                    d[v] = d[u] + G[u][j].dis;    //更新最短路径
        }
    }
}

对于多条最短路径、输出找到的路径,可以看这两篇哦:

Dijkstra算法进阶--多条最短路径情况

多条最短路径问题再探-使用Dijkstra+DFS选出最优路径

转载原创文章请注明,转载自: 斐斐のBlog » 最短路径 - 迪杰斯特拉(Dijkstra)算法详解
评论已关闭