精华内容
下载资源
问答
  • Dijkstra最短路径算法详解

    千次阅读 2015-08-06 00:26:44
    简介Dijkstra最短路径算法是非常经典图搜索算法,而且具有一定难度,需要花时间好好理解。算法导论第24章对此有详细分析,值得研究一番。而我自己也结合一个具体实例,实现了代码,确实只有在编码过程中才能...

    简介

    Dijkstra最短路径算法是非常经典的图搜索算法,而且具有一定难度,需要花时间好好理解。算法导论第24章对此有详细的分析,值得研究一番。而我自己也结合一个具体实例,实现了代码,确实只有在编码的过程中才能理解算法的细节,提高自己的算法能力。

    实例分析

    1.分步解析

    Dijkstra最短路径算法也叫单源最短路径算法,意思就是只需要输入一个起点,求出该起点到图中其余点的最短路径即可。(而floyd则是求任意两点间的最短路径)
    假如有如下有向图(无向图也可以,不能存在负值的边):
    这里写图片描述

    依旧使用二维数组存储这幅图的点和边:
    这里写图片描述

    还需要一个distance数组,用于存储起点到其余终点的最短距离:
    这里写图片描述

    假设我们的起点即为1号顶点,由上图可知,此时它只有到点2,点3两条路。要找点1到剩余2,3,4,5,6号顶点的最短距离,那么当然只能先到点2,或点3,再到4,5,6号点。而应该通过走边(1–>2) 还是走边 (1–>3)再走到其他的点呢?相信正常人都会走最短的那条,也就是边(1–>2)。

    也就是说,此时,我们要距离起点1,距离最近的点作为中转点,也就是2号点,将它加入到最短路径记录数组中。
    既然选择了走2号点,那么从2号点出发,有两条路可走,先讨论通过(2–>3)这条边能否让1号顶点到3号顶点的路程变短。也就是说现在来比较distance[3]和distance[2]+e[2][3]的大小。其中distance[3]表示1号顶点到3号顶点的路程。distance[2]+e[2][3]中distance[2]表示1号顶点到2号顶点的路程,e[2][3]表示(2–>3)这条边。所以distance[2]+e[2][3]就表示从1号顶点先到2号顶点,再通过2->3这条边,到达3号顶点的路程。

    我们发现原来的distance[3]=12,而distance[2]+e[2][3]=1+9=10,distance[3]>distance[2]+e[2][3],因此dis[3]要更新为10。这个过程在算法导论中的专业术语叫做边的“松弛”。1号顶点到3号顶点的路程即distance[3],通过2->3这条边松弛成功。这便是Dijkstra算法的主要思想:通过“边”来松弛1号顶点到其余各个顶点的路程。

    同理,通过边(2–>4)(即e[2][4]),可以将distance[4]的值从∞松弛为4(distance[4]初始为∞,distance[2]+e[2][4]=1+3=4,distacne[4]>distance[2]+e[2][4],因此dis[4]要更新为4)。

    此时,对2号顶点所有的出边进行了松弛。松弛完毕之后distance数组为:
    这里写图片描述

    因为2号顶点加入了最短路径中转记录数组中,所以继续找剩下的3,4,5,6号顶点,找出它们之中距离1号起点最近的点。显然,此时点4距离起点最近,所以把点4加入最短路径中转记录数组,然后对点4的所有出边(4->3,4->5和4->6)进行松弛操作。
    松弛完毕后最短路径数组变化为:
    这里写图片描述

    继续在剩下的3,5,6号点中寻找离起点距离最近的顶点作为中转点,这次找到3号。对3号顶点的所有出边(3->5)进行松弛后:
    这里写图片描述

    继续在剩下的5和6号顶点中,选出离1号顶点最近的顶点,这次选择5号顶点,对5号顶点的所有出边(5->4)进行松弛:
    这里写图片描述

    最后只剩下6号点了,由于6号点没有出边,所以就不用松弛了。

    2.代码实现:

    //创建图
    void createGraph(int graph[][POINTS]) {
        int mid_tmp,
            points_num,
            edges_num;
        //获取点数 & 边数
        scanf("%d %d",&points_num,&edges_num);
    
        //全部初始化为正无穷
        for (int i = 1;i <= points_num;++i)
            for (int j = 1;j <= points_num;++j) {
                    if (i == j)
                        graph[i][j] = 0;
                    else
                        graph[i][j] = INF;
            }
    
        //输入边
        int m,n,length;
        for (int i = 1;i <= edges_num;++i) {
            scanf("%d %d %d",&m,&n,&length);
            graph[m][n] = length;
        }
    }
    void showGraph(int graph[][POINTS],int n) {
    
        for(int i=1;i<=n;i++){    
            for(int j=1;j<=n;j++) {   
                printf("%10d",graph[i][j]);   
            }   
            printf("\n");   
        }
    }   
    /单源最短路径Dijkstra算法
    void dijkstra(int graph[][POINTS],int points,int start_point) {
        int distance[POINTS],  //从起点到其他顶点的最短距离数组
            record[POINTS];   //新加入中转顶点记录数组
    
        //Stpe 1:初始化工作
        memset(distance,INF,sizeof(distance));
        for (int i = 1;i<points; ++i) 
            distance[i] = graph[start_point][i];     
            //up^: 一开始只有与起点联通的点有距离,其余均不可到达
    
        for (int i = 1;i<points; ++i) 
            record[i] = 0;
        record[start_point] = 1; //开始时只有起点加入标记集合中
    
        //***最短路径主循环***//
        int min,min_mid_ponit;
        for (int i = 1; i<= points - 1; ++i) { //找剩余的n-1个点
    
            //Step 2:寻找离1号顶点距离最近的中转点,不断加入到标记集合中
            min = INF;
            for (int j = 1; j <= points; ++j) {
                if (record[j] == 0 && distance[j] < min) {
                    min = distance[j];
                    min_mid_ponit = j;
                }
            }
            record[min_mid_ponit] = 1;  
            //up^:找到此时距离起点距离最近的点,将该点加入已知集合中
    
            //Step 3:通过新加入的最近中转点,更新起点到其余各点的最短路径
            int end_ponit;
            for( end_ponit = 1; end_ponit <= points; ++end_ponit ) {
                //最近中转点到终点有路可达
                if ( graph[min_mid_ponit][end_ponit] < INF ) { 
                    if ( distance[end_ponit] > distance[min_mid_ponit] + graph[min_mid_ponit][end_ponit] ) 
                        distance[end_ponit] = distance[min_mid_ponit]+graph[min_mid_ponit][end_ponit]; 
                        //up^:更新最短路径  
                }
            }
        }
    
        //输出最终的结果
        cout<<"从起点"<<start_point<<"到其余各点的最短距离为:"<<endl;
        for( int i=1;i <= points; ++i )
            printf("%d ",distance[i]);
    }
    

    主函数

    int main(void) {
        int graph[POINTS][POINTS];
    
        createGraph(graph);
        showGraph(graph,6);
        //floyd(graph,4);
        dijkstra(graph,6,1);
    
        system("pause");
        return 0;
    }

    运行结果:

    这里写图片描述

    Ps:Dijkstra算法还可以用priority_queue或者斐波那契堆来进行优化。

    展开全文
  • 求某个结点到其他所有结点的最短路径的长度的算法,叫单源最短路径算法,后者叫全源最短路径算法。 全源最短路径–Floyed算法 设图 G(V,E)(有向无向都无所谓,Floyed算法不关心,下面Dijkstra同) 用邻接矩阵来...

    最短路径算法

    给定一个有向图或无向图 G(V,E) 有时我们需要求某个结点到其他所有结点的最短路径的长度,有时需要求出任意两个结点的最短路径。(如果是指定的两个结点间的最短路径可以直接暴搜,思维难度较低)。
    求某个结点到其他所有结点的最短路径的长度的算法,叫单源最短路径算法,后者叫全源最短路径算法。

    全源最短路径–Floyed算法

    设图 G(V,E)(有向无向都无所谓,Floyed算法不关心,下面Dijkstra同)
    用邻接矩阵来保存。设dis[i][j] 为结点 i 与结点 j 之间的距离,如果i与j之间没有边相连,则初始化dis[i][j] 为 INF。

    我们能想到,结点i和j之间可能有一条边,但是这条边的长度不一定是i,j之间的最短路,因为 i 结点有可能经过其他结点的中转到达 j,有可能存在更短的道路。
    那么对于dis[i][j]数组,我们可以有另一种理解方式,不再是两结点的距离,而是不允许经过任何结点中转的 i 与 j 之间的最短路径。这个最初始的距离,我们暂时将他视为最短距离,只不过这个距离只能是 i 和 j 的直接距离。
    但是在实际中,i到达j是可以在别的结点进行中转的,甚至可能经过了很多结点的中转才能得到 i 到 j 的真正的最短路
    假如在上例中,我们只允许结点 1 作为中间点,来更新任意两个结点之间的这个“伪最短路径”。也就是说对于每个结点对(i,j),检查:
    i ----> 1 -----> j ** 这条路径,是否比直接 i ------> j 更短,
    那么,我如果想让结点 2 也参与中转呢?很简单,刚才 “只能用结点1中转” 的结果已经保存在dis[i][j]里面了,这时候只要直接再用结点2进行一次中转,得到的dis[i][j],就是“可以用结点1和结点2两个结点进行中转的,i 和 j 的 最短距离”,此时还是“伪最短距离”。
    也就是说,这个时候,任意两个结点的“最短距离”,不再是i,j的直接距离,而是:可以走1,可以走2,可以两个都走,反正1和2两个结点都能用了。
    这样一来,如果我想得到任意两点的 “真最短距离” ,只需要依次把所有结点都加入到 “可中转结点” 中就行了。
    见代码:

    for(int k=1;k<=n;k++)              //最外面枚举中转结点,n是结点个数
        for(int i=1;i<=n;i++)          //内部两层,尝试更新任意两点的最短路径
            for(int j=1;j<=n;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j] = dis[i][k]+dis[k][j];
    

    最外面一层循环,执行到第 a 层的意义是,允许使用编号 <=a 的结点作为中转结点
    很显然这个算法的时间复杂度是 O(n^3)

    Floyed算法的变种

    实际上Floyed算法还有一个名字叫 “Floyed-Warshall算法”,它可以用来求二元关系R的传递闭包
    现在dis[i][j] 不在表示i 与 j 的距离,现在表示 “i 和 j R 相关”,在有向图中体现为有一条 i 到 j 的边(j 到 i 不一定,有向图)。在传递闭包中,u与v R相关,v 与 w 关于R相关,则 u 与 w 也R相关。
    基本思想与前面的中转点思想一致,u 可能经过很多结点的 “相关”传递到w。具体见代码。

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j] = dis[i][j] || (dis[i][k]&&dis[k][j]);
    

    得到的dis[][] 就是有向图的传递闭包。

    单源最短路径–Dijkstra

    Dijkstra算法是单源最短路径算法,能求出任意一个源点到其他结点的最短路。
    当你开始研究Dijkstra之前有一件事必须要了解,这个算法不同于其他最短路径算法,它只能求 “所有边权均不为负” 的有向 and 无向图的最短路,原因下面说。
    用一个一维数组dis[],来保存源点到其他结点的最短路径。
    Dijkstra算法的基本思想:
    首先将所有结点分成两类,一类是已经确定了最短路径的结点,我叫它“白点”,第二类是还没确定最短路径的结点,我们叫它“蓝点”。下面都用下图来说明这个算法,我们令源点是 1 。首先将所有 dis[] 初始化为INF,因为此时所有点都是“蓝点”。然后将dis[1] = 0因为显然源点到源点的最短路就是0。然后开始算法。
    在这里插入图片描述
    首先我们找到此时距离源点最近的结点(也就是此时dis[u] 最小的u),直接将u从蓝点变成白点,然后枚举所有蓝点,并尝试用新 “白点”,更新蓝点的最短路径。第一轮显然只有源点一个结点变成白点,并且更新了蓝点2,3,4的dis[],在下一轮中,由于dis[2] = 2 最小,所以结点2被选出变成白点。
    在这里插入图片描述
    为什么是这样做?
    原因就是Dijkstra巧妙的贪心思想
    任何时候,只要你在 dis[] 数组中找到一个最小的 dis[u] ,那么这个dis[u],一定就是源点到u的最短路径
    在这里插入图片描述
    这个时候我也可以解释,为什么Dijkstra只能求 “没有负边权的最短路”。
    有负边权的贪心是错的
    有负边权的贪心是错的
    有负边权的贪心是错的
    在这里插入图片描述
    即使现在 dis[u] 最小了,由于中转点到u可能存在负值,所以u根本不能确定能不能变成白点。
    综上,Dijkstra的思想,就是不断在 dis[]里找最小,变成白点,用白点更新蓝点的dis[],再找最小… 这样一个流程。
    第三轮把结点3变成了白点,把所有结点都变成白点算法就完成了,再做一张图,剩下的咕咕咕。。其实可以脑补了应该。。
    在这里插入图片描述
    代码:

    memset(dis, 0x7f, sizeof(dis));          //dis初始化无限大
    memset(vis, 0, sizeof(vis));             //vis用来标记白点
    dis[1] = 0;                              //源点dis = 0 
    for(int i=1;i<=n;i++)
    {
    	int minn = 2147483647, index;         //找最小的dis[u], index用来记录u 
    	for(int j=1;j<=n;j++) 
    	{
    		if(!vis[j]&&dis[j]<minn)          //vis用来标记白点, 找最小的dis在蓝点里找 
    		{
    			minn = dis[j];
    			index = j;
    		}
    	}
    	vis[index] = 1;                 //index就是找到的dis[u]最小的u
    	                                //把它变成白点 
    	for(int j=1;j<=n;j++)
    	{
    		if(!vis[j]&&map[index][j]!=0)      //用白点更新蓝点, map[i][j]是邻接矩阵存图
    		    if(dis[index]+map[index][j]<dis[j])
    		        dis[j] = dis[index]+map[index][j];
    	}
    }
    

    没有优化Dijkstra算法的时间复杂度是O(n^2)

    涉及到本文知识的题目

    Floyed传递闭包+拓扑排序:洛谷P2419 Cow Contest S
    Floyed最短路:洛谷P1522 牛的旅行 Cow Tours
    Dijkstra1:洛谷P3371 【模板】单源最短路径(弱化版)
    Dijkstra2:洛谷P4779 【模板】单源最短路径(标准版)

    展开全文
  • Bellman-Ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就...

    Bellman-Ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。

    #include<stdio.h>
    
    void main() {
    	//dis数组存储1号顶点到各个顶点的距离,n表示顶点个数,m表示边数
    	//u,v,w分别储存输入的每行数据,表示从u到v的距离为w
    	//flag判断负权回路问题
    	int dis[10], i, k, n, m, u[10], v[10], w[10], flag;
    	int inf = 99999999; //默认为无限大
    	scanf("%d %d", &n, &m); //输入顶点个数和边个数
    
    	//读入边
    	for (i = 1; i <= m; i++) {
    		scanf("%d %d %d", &u[i], &v[i], &w[i]);
    	}
    
    	//初始化dis数字,默认到自己为0,到其余定点为无限大
    	for (i = 1; i <= n; i++) {
    		dis[i] = inf;
    	}
    	dis[1] = 0;
    
    	//Bellman-Ford算法核心
    	for (k = 1; k <= n - 1; k++) {
    		for (i = 1; i <= m; i++) {
    			if (dis[v[i]] > dis[u[i]] + w[i]) {
    				dis[v[i]] = dis[u[i]] + w[i];
    			}
    		}
    	}
    	
    	//判断是否存在负权回路
    	flag = 0;
    	for (i = 1; i <= m; i++) {
    		if (dis[v[i]] > dis[u[i]] + w[i]) {
    			flag = 1;
    		}
    	}
    
    	//输出结果
    	if (flag == 1) {
    		printf("存在负权回路");
    	}
    	else {
    		for (i = 1; i <= n; i++) {
    			printf("%d ", dis[i]);
    		}
    	}
    	system("pause");
    }

    可以看出时间复杂度为O(NM),Bellman-Ford算法能成立的原理也很简单,当dis[u[i]]的值改变时,dis[u[i]]+w[i]的值即dis[v[i]]也会跟着改变,这就是松弛,以此类推,一个顶点的dis值改变,后续和其相关的顶点dis值才有可能会跟着改变,即可算出每个顶点距离源点的最短距离。这样也就很容易看出,其实不需要每次for循环都对所有的边进行松弛。所以我们可以使用队列,将哪些改变的顶点放入队列,然后下次只针对这个顶点对应的边进行松弛即可。至于为什么只需要n-1此循环即可,以为n个顶点,最短距离最多需要n-1个边,即n-1此松弛,即从源点开始n-1轮松弛。

    通过队列方式优化Bellman-Ford算法:

    #include<stdio.h>
    
    void main() {
    	//n为顶点个数,m为边数,u,v,w表示顶点u到顶点v的距离为w
    	int n, m, i, j, k;
    	int u[8], v[8], w[8];
    	//first要比n最大值大1,next要比m的最大值大1,因为for循环式从1开始的
    	int first[6], next[8];
    	//dis记录源点到各个顶点的距离,book记录那些顶点在队列中
    	int dis[6] = { 0 }, book[6] = { 0 };
    	//定义一个队列
    	int que[101] = { 0 }, head = 1, tail = 1;
    	//表示正无穷
    	int inf = 99999999;
    
    	scanf("%d %d", &n, &m);
    
    	//初始化dis数组
    	for (i = 1; i <= n; i++) {
    		dis[i] = inf;
    	}
    	dis[1] = 0;
    
    	//初始化book,firtst
    	for (i = 1; i <= n; i++) {
    		book[i] = 0;
    		first[i] = -1;
    	}
    
    	//读入每一条边
    	for (i = 1; i <= m; i++) {
    		scanf("%d %d %d", &u[i], &v[i], &w[i]);
    		//表示第i条边其对应的边
    		next[i] = first[u[i]]; 
    		//表示第u[i]个顶点对应的第一个边为第i条,即通过一个顶点值从first数组和next数组得到所有对应边,此为邻接表
    		first[u[i]] = i;
    	}
    
    	//1号顶点入队
    	que[tail] = 1; tail++;
    	//标志1号顶点入队
    	book[1] = 1;
    
    
    	while (head < tail) {
    		//当前需要处理的队首顶点
    		k = first[que[head]];
    		//扫面当前定点对应所有的边
    		while (k != -1) {
    			//判断松弛
    			if (dis[v[k]] > dis[u[k]] + w[k]) {
    				dis[v[k]] = dis[u[k]] + w[k];
    				//判断是否在队列中
    				if (book[v[k]] == 0) {
    					//入队列
    					que[tail] = v[k];
    					tail++;
    					//标记顶点v[k]已经入队
    					book[v[k]] = 1;
    				}
    			}
    			k = next[k];
    		}
    		//取消标记
    		book[que[head]] = 0;
    		//出队列
    		head++;
    	}
    	//输出
    	for (i = 1; i <= n; i++) {
    		printf("%d ", dis[i]);
    
    	}
    	system("pause");
    }

    可以看出只有在每次循环所有边都要松弛的情况下时间复杂度才为O(NM)

    展开全文
  • Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则...

    Bellman-Ford算法

    Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。

    注意本算法是可以处理负边的

    代码如下

    #include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    const int MAX = 1000000;
    //BellmanFord算法是一个单源最短路径算法,和dijkstra算分有点像,但是该算法可以处理包含
    //负权重的最短路径处理
    
    /*
    6 个节点
    1000000 1000000 10 100000 30 100
    1000000 1000000 5 1000000 1000000 1000000
    1000000 1000000 1000000 50 1000000 1000000
    1000000 1000000 1000000 1000000 1000000 10
    1000000 1000000 1000000 20 1000000 60
    1000000 1000000 1000000 1000000 1000000 1000000
    
    结果
    D[0]   D[1]   D[2]   D[3]   D[4]   D[5]
    0   1000000   10     50     30     60
    
    //节点0到节点5的最短路径是0 4 3 5
    */
    
    
    void BellmanFord()
    {
        const int n = 6;
        int mat[6][6] =
        {
            1000000, 1000000, 10, 100000, 30, 100,
            1000000, 1000000, 5, 1000000, 1000000, 1000000,
            1000000, 1000000, 1000000, 50, 1000000, 1000000,
            1000000, 1000000, 1000000, 1000000, 1000000, 10,
            1000000, 1000000, 1000000, 20, 1000000, 60,
            1000000, 1000000, 1000000, 1000000, 1000000, 1000000 };
    
        int dis[n] = { 0 };
        int pre[n] = { 0 };
    
        //初始化部分
        for (int i = 0; i<n; i++)
        {
            dis[i] = (i == 0) ? 0 : MAX;
            pre[i] = -1;
        }
    
        //节点数量为n,所以做n-1次循环
        for (int i = 1; i<n; i++)
        {
            //这个是针对每一条表做松弛
            for (int j = 0; j<n; j++)
            {
                for (int k = 0; k<n; k++)
                {
                    if (mat[j][k]<MAX)
                    {
                        if (dis[k] > dis[j] + mat[j][k])
                        {
                            dis[k] = dis[j] + mat[j][k];
                            pre[k] = j;
                        }
                    }
                }
            }
        }
    
        //判定是否有回路,无解
        int flag = 1;
        for (int j = 0; j<n; j++)
        {
            for (int k = 0; k<n; k++)
            {
                if (mat[j][k]<MAX)
                {
                    if (dis[k] > dis[j] + mat[j][k])
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            if (flag == 0)
                break;
        }
    
        if (flag == 0)
            cout << "存在回路" << endl;
        else
        {
            //这个就和dijkstra算法很像
            for (int i = 0; i<n; i++)
                cout << dis[i] << "  ";
            cout << endl;
    
            int b = n - 1;
            while (b != -1)
            {
                cout << b << "  ";
                b = pre[b];
            }
        }
    
    }
    int main()
    {
        BellmanFord();
        system("pause");
    }
    
    
    
    
    展开全文
  • 十一长假后,同学们陆续开始做题,现在月底了,扩展题“-二值矩阵避障最短路径算法”只有7人上交了作业,其中能够运行有2人,分别是电子18级邵华薇同学、软工18级唐宇。这里提出表扬。 题目可能是有些难度,是我...
  • 是我太笨了,想不到这么巧妙方法,说出来呢其实就是迪杰斯特拉单源最短路径算法的一点扩展和变种,可能没见过所以就不会做!!!!!! 哦对,这题不是我自己做,是看了大佬博客,以下是链接,自取自取:传送...
  • 代码如下://算法求解问题:算法求解最短路径问题,但是要经过中间节点k而且文件输入格式难度也有所加大 //算法求解问题:算法求解最短路径问题,但是要经过中间节点k而且文件输入格式难度也有所加大...
  • 最近在做PAT时发现图论的一些题目需要对多条最短路径进行筛选,一个直接的解决办法是在发现最短路径的时候就进行判断,选出是否更换路径;另一个通用的方法是先把所有的最短路径记录下来,然后逐个判断。前者具有...
  • * 是求含“负权”图“单源最短路径一种算法,效率较低,代码难度较小。 * 其原理为连续进行松弛,在每次松弛时把每条边都更新一下, * * 1. 第一个节点到其他节点最小距离 * 2. 图任意一条最短路径...
  • 需要说明是,这里所关心不是从一个起点出发访问所有其他定点单条最短路径,这种问题的难度更大。单起点最短路径问题要求是一组路径,每条路径都从起点出发通向图中一个不同顶点,其中某些路径可能具有公共...
  • 最短路径谈动态规划和贪心算法

    千次阅读 2018-01-20 23:58:24
    最短路径,从当前最优考虑。 先考虑下面图 可以很容易地看出,如果使用贪心算法,从a到e路线将是:a->b->c->d->e,而采用动态规划路线则是:a->c->e。 贪心算法的优点是代码非常容易编写,缺点则是从...
  • 要对最短路径的算法非常的了解 明晰 那么做适当的修改 就可以 关键之处 次短的路径: 设u 到 v的边权重为cost 那么到v的次短路径要么是 到u的次短路径+cost;要么是到u的最短路径+cost; 那么就在dijkstra中 既要...
  • 最短路径 合集

    2019-09-27 14:22:06
    2.Bellman-Forddef:Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环...
  • 对于简单的求最短路径的问题,用Dijkstra算法就可以实现。当然,对于加了第二标尺的:比如:如果最短路径有多条,选择边权最小的(花费最小)或者是点权最大的(物质数目多的),也可以用Dijkstra算法,在路径相等的...
  • 还是继续解决赛码网上百度2017/2016秋招题目,...虽然是被标注为4星(百度题目中没有5星),但是题目相对难度还是一般,或许因为这个题目是针对应届生,应该是大多数并没有从事算法竞赛同学。但是无论难度如何,...
  • - ford(贝尔曼-福特)算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果...
  • 难度:4 描述 南将军统领着N个部队,这N个部队分别驻扎在N个不同城市。 他在用这N个部队维护着M个城市治安,这M个城市分别编号从1到M。 现在,小工军师告诉南将军,第K号城市发生了暴乱,南...
  • 思路:这题的难度主要是在建图上,建完图之后就是求单源最短路径问题。可用dijkstra算法.要注意他给出x坐标不是有序 。 #include #include #include #define MAX 999 struct Position { double x; double...
  • 多源点最短路径问题

    千次阅读 2016-03-29 12:55:10
    给定带权又向图G=(V,E),对任意顶点Vi和Vj,求顶点Vi到Vj的最短路径长度? 分析: Floyd算法代码很简单,但是理解起来有一定的难度。网上有很多解释方法,我自己思想还没有完全成熟,稍后在作补充。#include ...
  • 如果已经明白了迪杰斯特拉算法而想知道花费问题、城市之间物资问题、最短路径条数问题朋友可以往下翻。。。。 一、迪杰斯特拉算法讲解 算法思想是从起点开始,找到一条起点能到达顶点中边权最小那个点,...
  • 点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | P.yh来源 | 五分钟学算法今天分享题目来源于 LeetCode 第 864 号问题:获取所有钥匙的最短路径。题目难度为 Hard,如果不借助 ...
  • 难度:4 描述 一个街区有很多住户,街区街道只能为东西、南北两种方向。 住户只可以沿着街道行走。 各个街道之间间隔相等。 用(x,y)来表示住户坐在街区。 例如(4,20),表示用户在东西方向第4...
  • 最短路径的O(ElgV)的解法。 使用邻接表存储图,使用堆操作选取下一个最小路径点。 本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高...
  • 本题就是使用Floyd算法求全部路径的最短路径,并且须要保存路径,并且更进一步须要依照字典顺序输出结果。 还是有一定难度的。 Floyd有一种非常巧妙的记录数据的方法,大多都是使用这种方法记录数据的。 只是事实...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 有一只特别狼,它在每个夜晚会进行变色,研究发现它可以变成N种颜色之一,将这些颜色标号为0,1,2…N-1。研究发现这只狼基因中存在一个变色...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 139
精华内容 55
关键字:

最短路径的算法难度