贪心算法Dijkstra-6ren

贪心算法Dijkstra

转载作者：我是一只小鸟更新时间：2023-01-01 22:33:31

Dijkstra

最短路径问题 : 给定一个带权有向图 G = (V, E, W) ，同时给定一个源点 u (u ∈ V)，我们要找出从源点 u 出发到其它各点的最短路径距离，并得出这些最短路径的具体路径有哪些边构成.

其实我们要求的就是从源点 u 出发到其它各点 str的最短路径所组成的路线网络，也就是一个最短路径树 .

我们以下面这个带权有向图为示例。

我们若以 A 为源点，得到如下的最短路径。

我们可以把源点到各点最短路径用绿色标记一下。

我们可以看出所有的最短路径构成了一个最短路径树。

我们要求的从源点到其它各点的最短路径所组成的路线网络，就是这个最短路径树.

在上面的图中，我们不难发现，当我们确定了源点 u 到某个其它的点 v 的最短路径时，在这个最短路径的具体路线中，若有一个中转点 t ，那么在这个最短路径中从源点 u 到 t 的路径也一定是 u 到 t 的最短路径 (之一)。也就是说，假设源点 u 到 v 的最短路径为 p ，那么 p 任意的前缀路径 q 一定是最优的(最短路径之一)。如果 q 不是最优的，那么就会存在另一个更短的路径比 p 更短.

这个性质还是很重要的，是解决单源最短路径问题的核心。

我们画个图来理解一下。

歧义性。

在上面的阐述中也稍微提到一点，就是最短路径其实不一定是唯一的，有可能存在两个路径，它们的路径距离一样且都是最短的，那么此时我们二选其一就可以啦。还有一个问题就是，我们的边权都应当是正数，如果边权存在非正数，那么我们是无法定义这个图中的最短路径的(距离确实不能是非正数呀，除了自己到自己🤔).

无环性。

这个性质其实很好理解，既然我们得到的所有最短路径构成的是一个最短路径树，那么作为一个树，它必不会存在环。也可以由之前的单调性得出这个性质.

Dijkstra 算法是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年提出的，一般解决的是带权有向图的单源最短路径问题。接下来介绍如何用 Dijkstra 算法求解单源最短路径问题 .

Dijkstra 算法将会充分利用最短路径树的单调性这一性质。先定下源点 u ，然后采用贪心的策略，不断去访问与源点 u 相接且之前未被访问过的最近的顶点 v (这句话里相接的意思是指可以从 u 到达 v )，使得当前的最短路径树得到扩充，一直到所有顶点都在当前的最短路径树中，那么就得到了源点 u 到其他所有顶点 v 的最短路径.

我们将当前最短路径树所有的顶点所构成的集合称为集合S ，而不在当前最短路径树中的顶点所构成的集合称为集合V-S .

1、首先需要定义一个辅助数组 flag[] ，用于标记每个顶点是否处于当前的最短路径树中，后续我们将最短路径树称为集合S 。在初始情况下，我们会先将源点 u 划入集合S ,

2、然后我们需要再定义一个数组 dist[] ，用于记录当前从源点 u 到 v (v∈V-S)的最短路径距离，比如 dist[vi] 就表示 u 到 vi 的当前最短路径距离.

集合S 每一次扩充都需要选择当前不在集合S 中且到源点 u 最短距离的顶点 t 作为扩充点，并且将其划入集合S 。之后的扩充操作中，就以这个 t 作为中转点对 dist[v] 进行更新，使其记录的距离减小。在不断扩充集合S 的过程中， dist[v] 的记录的距离大小不断减小(可能不变)，直到最后，其记录的便是整个图中 u 到 v 的最短的距离；。

另外，一开始我们要先初始化源点 u 到其邻接的顶点的距离.

3、为了还原具体路径，我们还需要一个辅助数组 pre[] ，用于记录最短路径中每个顶点的前驱顶点。比如 pre[v] ，其记录的是 u 到 v 的最短路径中，顶点 v 的前驱顶点。在不断扩充集合S 的过程中，如果可以借助当前的扩充点 t 到达 v 的距离更短，我们也要更新 v 的前驱为 t ，即 pre[v] = t .

同样的，我们也要初始化源点 u 为其每个邻接顶点的前驱.

(2) 。

(3) 。

(4) 。

(5) 。

(6) 。

(7) 。

以下程序是基于图的邻接矩阵实现的。

                        
                          //距离记录数组 , 前驱数组
int dist[MAX], pre[MAX];  
//集合S标记数组。如果flag[i]=true,说明该顶点i已经加入到集合S(最短路径集合);否则i属于集合V-S
bool flag[MAX];            

void Dijkstra(Graph *G, int u){
    for(int v = 0; v < G->nodenums; v++){
        dist[v] = G->edge[u][v];  //初始化源点u到各邻接点v的距离
        flag[v] = false;
        if(dist[v] != INF)
            pre[v] = u;           //若有邻接边,顶点v有前驱顶点u
        else
            pre[v] = -1;          //若没有,先初始化为-1
    }
    flag[u] = true;               //初始化集合S,只有一个元素: 源点u
    dist[u] = 0;                  //初始化源点u到自己的最短路径为0
    
    
    for(int i = 0; i < G->nodenums; i++){
    	int tmp = INF, t = u;
        /*  在集合V-S中寻找距离源点u最近的顶点t,使当前最短路径树最优  */
    	for(int v = 0; v < G->nodenums; v++){
    	    if(!flag[v] && dist[v] < tmp){
                //不在集合S中 并且 更小距离
                t = v;           
                //记录在V-S中距离源点u最近的顶点v
                tmp = dist[v];
    	    }
    	}

    	if(t == u)
    	    return;               //未找到直接终止
    	flag[t] = true;           //否则, 将t加入集合S
        
        /*   更新集合V-S中与t邻接的顶点到u的距离,扩展当前最短路径树  */
    	for(int v = 0; v < G->nodenums; v++){
            //不在集合S中 且 有边
    	    if(!flag[v] && G->edge[t][v] != INF){
                if(dist[v] > dist[t] + G->edge[t][v]){
                    //源点u可以借助t到达v的距离更短
                    dist[v] = dist[t] + G->edge[t][v];
                    pre[v] = t;
                }
    	    }
    	}
    }
}

还原具体路径代码。

我使用了 C++ 自带的栈 stack ，来实现最短路径具体路径的还原。因为记录的是每个顶点的前驱，所以恰好可以利用栈 stack 的先进后出的性质.

                        
                          //还原源点u到各点具体路径
void ShowShortPath(Graph G, int u){
    for(int v = 0; v < G.nodenums; v++){
        if(dist[v] == INF || dist[v] == 0)
            continue;
        cout<<"\n点"<<G.apex[u]<<" 到 点"<<G.apex[v]<<" 的最短路径距离为: "<<dist[v]<<endl;
        cout<<"点"<<G.apex[v]<<"的前驱顶点为: 点"<<G.apex[pre[v]]<<endl;
        cout<<"具体路径为: "<<endl;

        int t = pre[v];           //终点的前驱下标
        //用栈存储终点前驱们 一直到 源点
        stack<int> st;            
        while(t != u){
            st.push(t);
            t = pre[st.top()];
	}

    cout<<G.apex[u];          		//源点
	while(!st.empty()){
	    t = st.top();
	    cout<<" --> "<<G.apex[t];   //中间点
	    st.pop();
        }
	cout<<" --> "<<G.apex[v]<<endl; //终点
	cout<<"———————————————————"<<endl;
    }
}

完整程序(含图的邻接矩阵) 。

                        
                          #include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int MAX = 100;
const int INF = 1e7;

typedef char ApexType;			//顶点名称数据类型
typedef int EdgeType;			//边权数据类型

typedef struct {

	ApexType apex[MAX];			//顶点表
	EdgeType edge[MAX][MAX];	//矩阵图
	int nodenums, edgenums;		//顶点个数，边个数

}Graph;

//创建邻接矩阵
void CreateGraph(Graph *G){
    int i, j, k;
    int w;
    cout<<"输入顶点个数和边的条数: ";
    cin>>G->nodenums>>G->edgenums;
    //输入顶点信息
    for(i = 0; i < G->nodenums; i++){
	cout<<"输入第 "<<i + 1<<" 个顶点的名称: ";
	cin>>G->apex[i];
    }
    //初始化各顶点之间的边为无穷大
    for(i = 0; i < G->nodenums; i++)
	for(j = 0; j < G->nodenums; j++)
	    G->edge[i][j] = INF;             
    //录入有向边的信息
    for(k = 0; k < G->edgenums; k++){
        EdgeType w;
        cout<<"输入<vi, vj>的对应点下标及权值: ";
        cin>>i>>j>>w;
        G->edge[i][j] = w;
    }
}

//打印图的邻接矩阵
void ShowGraphInMatrix(Graph *G){
    cout<<"   ";
    for(int i = 0; i < G->nodenums; i++)
		printf("%4c",G->apex[i]);
    cout<<endl;

    for(int i = 0; i < G->nodenums; i++){
		printf("%3c", G->apex[i]);
        for(int j = 0; j < G->nodenums; j++){
            if(G->edge[i][j] == INF)
                cout<<"∞  ";
            else
                printf("%4d", G->edge[i][j]);
        }
		cout<<endl;
    }		
}

//距离记录数组 , 前驱数组
int dist[MAX], pre[MAX];  
//集合S标记数组。如果flag[i]=true,说明该顶点i已经加入到集合S(最短路径集合);否则i属于集合V-S
bool flag[MAX];            

void Dijkstra(Graph *G, int u){
    for(int v = 0; v < G->nodenums; v++){
        dist[v] = G->edge[u][v];  //初始化源点u到各邻接点v的距离
        flag[v] = false;
        if(dist[v] != INF)
            pre[v] = u;           //若有邻接边,顶点v有前驱顶点u
        else
            pre[v] = -1;          //若没有,先初始化为-1
    }
    flag[u] = true;               //初始化集合S,只有一个元素: 源点u
    dist[u] = 0;                  //初始化源点u到自己的最短路径为0
    
    /*   在集合V-S中寻找距离源点u最近的顶点t,使当前最短路径树最优  */
    for(int i = 0; i < G->nodenums; i++){
    	int tmp = INF, t = u;
    	for(int v = 0; v < G->nodenums; v++){
    	    if(!flag[v] && dist[v] < tmp){
                //不在集合S中 并且 更小距离
                t = v;            
                //记录在V-S中距离源点u最近的顶点v
                tmp = dist[v];
    	    }
    	}

    	if(t == u)
    	    return;               //未找到直接终止
    	flag[t] = true;           //否则, 将t加入集合S
        
        /*   更新集合V-S中与t邻接的顶点到u的距离,扩展当前最短路径树  */
    	for(int v = 0; v < G->nodenums; v++){
    	    if(!flag[v] && G->edge[t][v] != INF){
    		//不在集合S中 且 有边
                if(dist[v] > dist[t] + G->edge[t][v]){
                    //源点u可以借助t到达v的距离更短
                    dist[v] = dist[t] + G->edge[t][v];
                    pre[v] = t;
                }
    	    }
    	}
    }
}

//还原源点u到各点具体路径
void ShowShortParth(Graph G, int u){
    for(int v = 0; v < G.nodenums; v++){
	if(dist[v] == INF || dist[v] == 0)
	    continue;
	cout<<"\n点"<<G.apex[u]<<" 到 点"<<G.apex[v]<<" 的最短路径距离为: "<<dist[v]<<endl;
	cout<<"点"<<G.apex[v]<<"的前驱顶点为: 点"<<G.apex[pre[v]]<<endl;
	cout<<"具体路径为: "<<endl;

	int t = pre[v];           //终点的前驱下标
	//用栈存储终点前驱们 一直到 源点
	stack<int> st;            
	while(t != u){
	    st.push(t);
	    t = pre[st.top()];
	}

    	cout<<G.apex[u];          		//源点
	while(!st.empty()){
	    t = st.top();
	    cout<<" --> "<<G.apex[t];   //中间点
	    st.pop();
        }
	cout<<" --> "<<G.apex[v]<<endl; //终点
	cout<<"———————————————————"<<endl;
    }
}


main(){
    Graph G;
    CreateGraph(&G);
    ShowGraphInMatrix(&G);
    
    int u;
    cout << "\n输入出发的源点下标: ";
    cin>>u;

    Dijkstra(&G, u);
    
    cout<<"\n源点到所有点的单源最短路径距离:"<<endl;
    ShowShortParth(G, v);
}

结果。

单源最短路径及具体路径。

原文链接:[ 最短路径问题]Dijkstra算法(含还原具体路径) - Amαdeus - 博客园 (cnblogs.com) 。

最后此篇关于贪心算法Dijkstra的文章就讲到这里了,如果你想了解更多关于贪心算法Dijkstra的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： Django模型层

文章推荐： C#开发的线程池和管理器-开源研究系列文章

文章推荐：详解前端缓存，解决前端换包之后环境中仍会出现旧版效果

文章推荐： Redisset数据类型命令使用及应用场景使用总结

Python 正则表达式或 |贪心
>>> import re >>> p = re.compile('.*&l=(.*)(&|$)') >>> p.search('foo&l=something here&bleh').group(1
algorithm - 最大化回车算法的#(贪心？)
最近有一道面试题如下:我们得到了一个单词列表，我们想要格式化它们以最大化回车符的数量，同时将每行的字母数量保持在一个范围内。例如，我们希望每行的字母范围为 5 - 10(含)，一种解决方案是: he
arrays - 如何找到最近的N个网格点(贪心)
我正在使用二维数组来处理游戏中的对象。数组的维度就像笛卡尔网格上的坐标。当玩家选择一个点时，我想从数组中收集 N 个最近的网格单元，即使该点不是有效的数组索引。例子:从 [0,0] 到 [10,10
odata - Olingo 贪心 $expand
我在 Hibernate 之上使用 Olingo 1.2。我有一个返回 250 行的请求，每行以一对多关系链接到另一个表。我执行 $expand 以获取子表中的所有数据，但是当我检查在数据库中执行
regex - 贪心 block ()* 包含通配符
我正在 ANTLR4 中构建语法，但收到此警告 TL4.g4:224:12: greedy block ()* contains wildcard;非贪婪语法 ()*?可能是首选这是它引用的代码行
c# - 贪心 JoinBlock 解释
In the default greedy mode, all data offered to targets are accepted, even if the other target doesn
algorithm - 有什么更好的方法来解决这个(贪心？)问题
假设我有 n 个盒子，每个盒子里面都有一些值 b[i] .我可以保证对一组框进行排序，使得 b[1] j; { min_{k=i}^j (c[k] + max(T(i, k-1)
刷爆LeetCode周赛339，贪心/排序/拓扑排序/平衡二叉树
本文已收录到 AndroidFamily ，技术和职场问题，请关注公众号 [彭旭锐] 提问。大家好，我是小彭。上周末是 LeetCode 第 339 场周赛，你参加
php - PHP 中的“贪心 token 解析”
什么是 PHP 中的“贪心 token 解析”？我在 Codeigniter 指南中找到了这个: “除非需要解析变量，否则始终使用单引号字符串，并且在确实需要解析变量的情况下，使用大括号防止贪婪的标记
刷爆LeetCode周赛337，位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心
本文已收录到 AndroidFamily ，技术和职场问题，请关注公众号 [彭旭锐] 提问。大家好，我是小彭。上周末是 LeetCode 第 337 场周赛，你参加

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

贪心算法Dijkstra

Dijkstra