本文主要是介绍单源最短路径问题--Dijkstra算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Dijkstra算法实现
- 1.算法过程
- 2.代码实现过程
- 2.1朴素Dijkstra实现
- 2.2朴素Dijkstra实现
1.算法过程
Dijkstra算法是图论中用来解决单元最短路径的算法,我们通过将点划分成为两个部分,一个是已经确定了源点到达此处最短路径的点,另外一个部分是还不确定最短路径的点。我们每次每一次选择状态图中最短路,将最短路端点A标记成为已经确定最短路径的点集,接着看看是否有通过A这个最短路径可以有一条更短的路到达未确定的点,如果有的话,就更新源点到达这个点路径的最短信息。接着重复找到最短的路径加入,重复上面步骤,指导所有点都找完。确切算法描述过程如下:
在算法实现过程中,每次选择最短路径和更新路径信息是耗时较多的地方,所以我们选择最短路的时候,是否通过堆来优化,将Dijkstra算法划分成为了朴素Dijkstra(就是没次选择最短路加入的时候,需要将所有路径长度遍历一次)和堆优化的Dijkstra。
2.代码实现过程
这里以leecode中题目为例子来讲述Dijkstra的实现过程,代码是参考灵茶山艾府的题解
2.1朴素Dijkstra实现
注意朴素Dijkstra的实现利用的图的存储结构是邻接矩阵
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2));//邻接矩阵存储for(auto &t : times){g[t[0] - 1][t[1] - 1] = t[2];}//dis用来存储单元的最短的路径;done用来标记是否已经确定了最短路径vector<int> dis(n, INT_MAX / 2), done(n);//顶点k作为源点dis[k - 1] = 0;while(true){int x = -1;for(int i = 0; i < n; i++){//用来确定最短路径:x是用来标记确定最短路径的另一端的点if(!done[i] && (x < 0 || dis[i] < dis[x])){x = i;}}//表示已经确定了所有点的最短路径if(x < 0) return ranges::max(dis);//有节点无法到达if(dis[x] == INT_MAX / 2) return -1;//最短路长度已经确定,无法变得更小done[x] = true;//确定源点到达x最短路径之后,需要判断是否更新源点到达x相连点的路径长度for(int y = 0; y < n; y++){//更新x的邻居的最短路dis[y] = min(dis[y], dis[x] + g[x][y]);}}}
};
2.2朴素Dijkstra实现
堆优化实现的过程中,需要去把这个判断语句的作用给弄明白
if(dx > dis[x]) continue;
这个因为我们利用堆实现的过程中,我们确定了最短路径的点加入之后,我们的更新路径的信息过程不会直接去把堆中的信息给修改,而是直接再插入一个更短的路径信息上去。
例如下图:我们源点确定了之后,会将源点相连的点1和点2的路径信息更新为3和10(其余点为无穷),
但是接下我们堆中的最短路径长度3(源点到达点1),此时通过点1我们发现源点到达点2的距离可以有一条比长度10更短的路径长度7,但是此时我们不会直接去将堆中的10给删除,而是插入一个7。同时记住一下到达点2的路可以用7就到达,所以之后我们堆弹出10的时候,我们不会拿着10(脏数据)去更新点2的最短路径。
class Solution {
public://邻接表适合稀疏图int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> g(n);//邻接表for(auto &t :times){//x -> y: 把y和x到y距离打包成pair拉链到点x下面g[t[0] - 1].emplace_back(t[1] - 1, t[2]);}//存储最短路径vector<int> dis(n, INT_MAX);//从源点k出发dis[k - 1] = 0;//定义一个最小堆,维护源点到达其他顶点未选择路径的最短路(第二个参数指名了底层实现的堆的数据结构)priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;//pq中的pair为:<distance, point>pq.emplace(0, k - 1);while(!pq.empty()){auto [dx, x] = pq.top();pq.pop();//x之前出堆过(对于同一个 x,入堆的 dis[x] 只会越来越小,那么首先弹出的就是最小的 dis[x],//后面弹出的 dx 必定比 dis[x] 大。既然首先弹出的是最小的,所以首次弹出的 dx 等于 dis[x])if(dx > dis[x]) continue;for(auto &[y, d] :g[x]){int new_dis = dx + d;if(new_dis < dis[y]){//跟新x的邻居的最短路dis[y] = new_dis;pq.emplace(new_dis, y);}}}int mx = ranges::max(dis);return mx < INT_MAX ? mx : -1;}
};
这篇关于单源最短路径问题--Dijkstra算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!