精华内容
下载资源
问答
  • 原文地址:http://www.wutianqi.com/?p=1912 相关文章: 1.Dijkstra算法: ... 2.Floyd算法: ... Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值

    原文地址:http://www.wutianqi.com/?p=1912

    相关文章:

    1.Dijkstra算法:

    http://www.wutianqi.com/?p=1890

    2.Floyd算法:

    http://www.wutianqi.com/?p=1903

    Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。Bellman-Ford算法的流程如下:
    给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,

    • 数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为, Distant[s]为0;
    •  
      以下操作循环执行至多n-1次,n为顶点数:
      对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;
      若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;
    • 为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

    可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

    首先介绍一下松弛计算。如下图:


     

    松弛计算之前,点B的值是8,但是点A的值加上边上的权重2,得到5,比点B的值(8)小,所以,点B的值减小为5。这个过程的意义是,找到了一条通向B点更短的路线,且该路线是先经过点A,然后通过权重为2的边,到达点B。
    当然,如果出现一下情况


     

    则不会修改点B的值,因为3+4>6。
     
    Bellman-Ford算法可以大致分为三个部分
    第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
    第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
    第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:
    d(v) > d (u) + w(u,v)
    则返回false,表示途中存在从源点可达的权为负的回路。
     
    之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
    考虑如下的图:
     

    经过第一次遍历后,点B的值变为5,点C的值变为8,这时,注意权重为-10的边,这条边的存在,导致点A的值变为-2。(8+ -10=-2)
     
     

    第二次遍历后,点B的值变为3,点C变为6,点A变为-4。正是因为有一条负边在回路中,导致每次遍历后,各个点的值不断变小。
     
    在回过来看一下bellman-ford算法的第三部分,遍历所有边,检查是否存在d(v) > d (u) + w(u,v)。因为第二部分循环的次数是定长的,所以如果存在无法收敛的情况,则肯定能够在第三部分中检查出来。比如
     

    此时,点A的值为-2,点B的值为5,边AB的权重为5,5 > -2 + 5. 检查出来这条边没有收敛。
     
    所以,Bellman-Ford算法可以解决图中有权为负数的边的单源最短路径问。

    个人感觉算法导论讲解很不错,把这一章贴出来和大家分享:

    24.1 The Bellman-Ford algorithm

    The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (VE) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.

    The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(sv). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.

    BELLMAN-FORD(G, w, s)
    1  INITIALIZE-SINGLE-SOURCE(G, s)
    2  for i1 to |V[G]| - 1
    3       do for each edge (u, v) ∈ E[G]
    4              do RELAX(u, v, w)
    5  for each edge (u, v) ∈ E[G]
    6       do if d[v] > d[u] + w(u, v)
    7             then return FALSE
    8  return TRUE

    Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the d and π values of all vertices in line 1, the algorithm makes |V| – 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.)

    (单击图片可以放大)

    Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then π[v] = u. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.

    The Bellman-Ford algorithm runs in time O(V E), since the initialization in line 1 takes Θ(V) time, each of the |V| – 1 passes over the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7 takes O(E) time.

    以下是Bellman-Ford代码:

    #include <iostream>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    
    /*
    Bellman-Ford:计算带有负权值的最短路径,注意:带有负环的最短路径无法求得
    
    算法思想:
    S1:初始化除源点外所有点的最短距离为无穷,源点距离为0
    S2:执行|V-1|次循环,每次对所有边进行松弛操作,即:如果d[u] + w(u,v) < d[v],则令d[v] = d[u] + w(u,v)
    S3:遍历每条边,对每条边检测是否可以继续松弛,即:如果d[u] + w(u,v) < d[v],说明存在负环,无法计算最短距离;若每条边都不可以松弛,
    则d[i]表明源点到节点i的最短距离
    输出:
    如果存在负环,输出:存在负环
    如果不存在负环,按照节点下标从小到大的顺序,输出:源点到各个节点的最短距离
    
    距离数组的大小与顶点个数相同
    
    输入:
    3(边数) 3(顶点数) 0(源点)
    0 1 5
    1 2 3
    2 0 -10
    输出:
    存在负环
    
    输入:
    10 5 0
    0 1 6
    0 2 7
    1 2 8
    1 3 5
    1 4 -4
    2 3 -3
    2 4 9
    3 1 -2
    4 0 2
    4 3 7
    输出:
    2 7 4 -2
    节点1到源点0的最短距离:2,路径:0 2 3 1
    节点2到源点0的最短距离:7,路径:0 2
    节点3到源点0的最短距离:4,路径:0 2 3
    节点4到源点0的最短距离:-2,路径:0 2 3 4
    
    */
    
    const int N = 10000;
    int d[N];
    int pre[N];
    typedef struct Edge
    {
    	Edge(){}
    	Edge(int iBeg , int iEnd , int iWeight):_iBeg(iBeg),_iEnd(iEnd),_iWeight(iWeight){} 
    	void setEdge(int iBeg , int iEnd , int iWeight)
    	{
    		_iBeg = iBeg;
    		_iEnd = iEnd;
    		_iWeight = iWeight;
    	}
    	int _iBeg, _iEnd;
    	int _iWeight;
    }Edge;
    
    
    
    bool bellmanFord(int iStart ,int iVertexNum , int iEdgeNum , Edge* pEdge)
    {
    	if(!pEdge)
    	{
    		return false;
    	}
    	//设定起始节点的前向节点为本身,用于打印单源最短路径
    	memset(pre, -1 , sizeof(pre));
    	pre[iStart] = iStart;
    	//初始化,对除源点外的顶点距离设置为无穷大
    	for(int i = 0 ; i < iVertexNum ; i++ )
    	{
    		if(i != iStart)
    		{
    			d[i] = INT_MAX;
    		}
    		else
    		{
    			d[i] = 0;
    		}
    	}
    	//迭代|V|-1次,每次对所有边进行松弛
    	for(int i = 0 ; i < iVertexNum - 1 ; i++)
    	{
    		//对每条边遍历,进行松弛处理
    		for(int j = 0 ; j < iEdgeNum ; j++)
    		{
    			int u = pEdge[j]._iBeg;
    			int v = pEdge[j]._iEnd;
    			int iWeight = pEdge[j]._iWeight;
    			//如果起点的距离值+边的权重<终点的距离值,就进行松弛处理
    			if(d[u] + iWeight < d[v])
    			{
    				d[v] = d[u] + iWeight;
    				//记录每次松弛后终点的前面的端点为
    				pre[v] = u;
    			}
    		}
    	}
    	//负权检测:遍历所有边,检测是否还可以继续松弛,如果是,表明存在负环,无法计算单源最短路径
    	for(int j = 0 ; j < iEdgeNum ; j++)
    	{
    		int u = pEdge[j]._iBeg;
    		int v = pEdge[j]._iEnd;
    		int iWeight = pEdge[j]._iWeight;
    		//如果起点的距离值+边的权重<终点的距离值,就进行松弛处理
    		if(d[u] + iWeight < d[v])
    		{
    			return false;
    		}
    	}	
    	return true;
    }
    
    //打印路径,参数root:当前端点下标,采用先递归后打印的方式
    void printPath(int root)
    {
    	//递归基
    	if(pre[root] == root)
    	{
    		//打印起始节点
    		cout << root << " ";
    		return;
    	}
    	printPath(pre[root]);
    	cout << root << " " ;
    }
    
    void process()
    {
    	int iVertexNum , iEdgeNum , iStart;
    	Edge edgeArr[N];
    	while(cin >> iEdgeNum >> iVertexNum >> iStart)
    	{
    		//生成边
    		for(int i = 0 ; i < iEdgeNum ; i++)
    		{
    			cin >> edgeArr[i]._iBeg >> edgeArr[i]._iEnd >> edgeArr[i]._iWeight;
    		}
    		//调用贝尔曼-福特算法
    		if(bellmanFord(iStart ,iVertexNum , iEdgeNum , edgeArr))
    		{
    			for(int i = 0 ; i < iVertexNum ; i++ )
    			{
    				if(i != iStart)
    				{
    					cout << "节点" << i << "到源点" << iStart << "的最短距离:" << d[i] << ",路径:";
    					printPath(i);
    					cout << endl;
    				}		
    			}
    			
    		}
    		else
    		{
    			cout << "存在负环" << endl;
    		}
    	}
    }
    
    int main(int argc,char* argv[])
    {
    	process();
    	system("pause");
    	return 0;
    }



    补充:
    考虑:为什么要循环V-1次?
    答:因为最短路径肯定是个简单路径,不可能包含回路的,
    如果包含回路,且回路的权值和为正的,那么去掉这个回路,可以得到更短的路径
    如果回路的权值是负的,那么肯定没有解了

    图有n个点,又不能有回路
    所以最短路径最多n-1边

    又因为每次循环,至少relax一边
    所以最多n-1次就行了



    展开全文
  • 最短路径问题

    2018-03-23 10:42:03
    非加权图的最短路径采用广度优先搜索,它按层处理一层的所有结点:离起始结点最近的结点最先处理,距离最远的最晚处理。具体过程: 从s到s的最短路径为0; 通过搜索s的所有邻接结点就能找到离s距离为1的所有结点;

    最短路径问题

    • 单源最短路径

      • 非加权图的最短路径

      • 加权图的最短路径

      • 带有负权值的图
      • 有向无环图
    • 所有顶点对间的最短路径

    单源最短路径

    给出一个加权图和图上的一个节点s,找出s到图中每一节点的最短路径。

    非加权图的最短路径

    采用广度优先搜索,它按层处理一层的所有结点:离起始结点最近的结点最先处理,距离最远的最晚处理。

    具体过程:

    1. 从s到s的最短路径为0;
    2. 通过搜索s的所有邻接结点就能找到离s距离为1的所有结点;
    3. 搜索离s距离为1的所有结点的邻接结点就能找到距离为2的节点;
    4. 重复上述过程,直到所有节点都访问到为止。

    存储设计:

    • 数组distance:记录从源点到达每个结点的最短距离。

    • 数组prev:记录要到达此结点,必须到达的前一结点。用于追溯这条路径。

    加权图的最短路径

    Dijkstra算法:

    • 保存了一个顶点集S。S中的顶点是已经找到了最短路径的顶点。

    • 开始时,顶点集合S只包含源点s一个顶点。

    • 反复执行以下循环,直至顶点集S包含所有的顶点为止:对于在顶点集V - S中的每个顶点,考察新加入顶点集S中的结点是否有边到达V-S。如果存在,则检查这条路径是否比原来已知的路径要短。如果是,则更新源点到此结点的距离和路径;然后,从V – S中寻找一个路径最短的结点,从源点到这个结点已经不可能有更好的路径了,把它加入顶点集S。

    带有负权值的图

    如果一个图带有负权值的边,Dijkstra算法无法正常工作。

    实现:利用一个队列

    1. 开始时,将源点s放入队列
    2. 重复以下过程,直到队列为空:
      1. 出队一个节点v
      2. 对v的所有邻接点w,如果经过v到w的距离比已知的s到w的距离短,则更新w的距离,并将w入队

    有向无环图

    描述一项工程或系统进展的有效工具。

    AOV网(Activity On Vertex Network)

    将所有的工程项目分解为若干个活动(子工程);活动定义在顶点上,顶点之间的有向边表示活动执行的次序。

    AOE网(Activity On Edge Network)

    将所有的工程项目分解为若干个活动(子工程);活动定义在有向边上,顶点表示事件,有向边的权值表示活动持续的时间,有向边的方向表示事件发生的先后次序。

    关键事件和关键路径概念。

    所有顶点对间的最短路径

    方法一:对每一结点运行Dijkstra最短路径算法。

    方法二:Floyd算法。

    Floyd算法

    一次将每个节点作为中间节点,看看从起始点到中间结点,再从中间节点到终止点的距离是不是比已知的距离短。如是,则替代。

    使用n行n列的矩阵A用于计算最短路径。

    进行n次迭代。在进行第k次迭代时

    Ak[i,j]=min{Ak1[i,j],Ak1[i,k]+Ak1[k,j]}

    路径信息的保存需要一个二维数组prev。prev[i][j]的值表示从i到j的最短路径上的前一结点的序号。

    展开全文
  • 最短路径

    2016-06-08 14:13:40
    最短路径 Dijkstra(迪杰斯特拉 权值都是正...是解决任意两点间的最短路径的一种算法,可以正确处理有向图或权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂

    最短路径

    1. Dijkstra(迪杰斯特拉 权值都是正的)
      是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止
    2. Floyd(弗洛伊德 可以带负权值)
      是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)
    3. Bellman-Ford(伯尔曼 可以带负权值)

    原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

    展开全文
  • Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。 这时候,就需要使用其他的算法来求解最短路径,Bellman-...

    转载链接:http://www.wutianqi.com/?p=1912


    Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。

    这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特福特(Lester Ford)发明。

    适用条件&范围:

    单源最短路径(从源点s到其它所有顶点v);

    有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

    边权可正可负(如有负权回路输出错误提示);

    差分约束系统;

    Bellman-Ford算法的流程如下
    给定图G(V, E)(其中VE分别为图G的顶点集与边集),源点s数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n], Distant[s]0

    以下操作循环执行至多n-1次,n为顶点数:
    对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)w(u, v)为边e(u,v)的权值;
    若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;

    为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

    可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

    BellmanFord算法可以大致分为三个部分
    第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
    第二,进行循环,循环下标为从1n1n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
    第三,遍历途中所有的边(edgeuv)),判断是否存在这样情况:
    dv) > d (u) + w(u,v)
    则返回false,表示途中存在从源点可达的权为负的回路。
     
    之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。 

    测试代码如下:(下面为有向图的Bellman-Ford算法。。。。。)



    #include<iostream>
    #include<cstdio>
    using namespace std;
    
    #define MAX 0x3f3f3f3f
    #define N 1010
    int nodenum, edgenum, original; //点,边,起点
    
    typedef struct Edge //边
    {
    	int u, v;
    	int cost;
    }Edge;
    
    Edge edge[N];
    int dis[N], pre[N];
    
    bool Bellman_Ford()
    {
    	for(int i = 1; i <= nodenum; ++i) //初始化
    		dis[i] = (i == original ? 0 : MAX);
    	for(int i = 1; i <= nodenum - 1; ++i)
    		for(int j = 1; j <= edgenum; ++j)
    			if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~)
    			{
    				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
    				pre[edge[j].v] = edge[j].u;
    			}
    			bool flag = 1; //判断是否含有负权回路
    			for(int i = 1; i <= edgenum; ++i)
    				if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
    				{
    					flag = 0;
    					break;
    				}
    				return flag;
    }
    
    void print_path(int root) //打印最短路的路径(反向)
    {
    	while(root != pre[root]) //前驱
    	{
    		printf("%d-->", root);
    		root = pre[root];
    	}
    	if(root == pre[root])
    		printf("%d\n", root);
    }
    
    int main()
    {
    	scanf("%d%d%d", &nodenum, &edgenum, &original);
    	pre[original] = original;
    	for(int i = 1; i <= edgenum; ++i)
    	{
    		scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
    	}
    	if(Bellman_Ford())
    		for(int i = 1; i <= nodenum; ++i) //每个点最短路
    		{
    			printf("%d\n", dis[i]);
    			printf("Path:");
    			print_path(i);
    		}
    	else
    		printf("have negative circle\n");
    	return 0;
    }

    测试数据:

    4 6 1
    1 2 20
    1 3 5
    4 1 -200
    2 4 4
    4 2 4
    3 4 2

    和:

    4 6 1
    1 2 2
    1 3 5
    4 1 10
    2 4 4
    4 2 4
    3 4 2

    另:Dijkstra和Bellman-Ford算法对比

    • Dijkstra 
      dijkstra算法本质上算是贪心的思想,每次在剩余节点中找到离起点最近的节点放到队列中,并用来更新剩下的节点的距离,再将它标记上表示以后已经找到到它的最短路径,以后不用更新它了。这样做的原因是到一个节点的最短路径必然会经过比它离起点更近的节点,而如果一个节点的当前距离值比任何剩余节点都小,那么当前的距离值一定是最小的。(剩余节点的距离值只能用当前剩余节点来更新,因为求出了最短路的节点之前已经更新过了) 
      dijkstra就是这样不断从剩余节点中拿出一个可以确定最短路径的节点最终求得从起点到每个节点的最短距离。

    • Bellman-Ford 
      bellman-ford算法进行n-1次更新(一次更新是指用所有节点进行一次松弛操作)来找到到所有节点的单源最短路。bellman-ford算法和dijkstra其实有点相似,该算法能够保证每更新一次都能确定一个节点的最短路,但与dijkstra不同的是,并不知道是那个节点的最短路被确定了,只是知道比上次多确定一个,这样进行n-1次更新后所有节点的最短路都确定了(源点的距离本来就是确定的)。 
      现在来说明为什么每次更新都能多找到一个能确定最短路的节点:

    1.将所有节点分为两类:已知最短距离的节点和剩余节点。

    2.这两类节点满足这样的性质:已知最短距离的节点的最短距离值都比剩余节点的最短路值小。(这一点也和dijkstra一样)

    3.有了上面两点说明,易知到剩余节点的路径一定会经过已知节点

    4.而从已知节点连到剩余节点的所有边中的最小的那个边,这条边所更新后的剩余节点就一定是确定的最短距离,从而就多找到了一个能确定最短距离的节点,不用知道它到底是哪个节点。

    bellman-ford的一个优势是可以用来判断是否存在负环,在不存在负环的情况下,进行了n-1次所有边的更新操作后每个节点的最短距离都确定了,再用所有边去更新一次不会改变结果。而如果存在负环,最后再更新一次会改变结果。原因是之前是假定了起点的最短距离是确定的并且是最短的,而又负环的情况下这个假设不再成立。



    展开全文
  • 单源最短路径

    2017-09-08 14:48:01
    单源最短路径的种种…DP的算法单源最短路径的种种 DP的算法 NO1 only 5 lines Floyd算法 优缺点 基本概念 代码 NO2 Dijksra 算法 优缺点 基本概念 代码 NO3 Bellman-Ford 算法 ...1.可以处理负权值
  • 不能处理权值为负值的情形,Dijkstra算法在利用顶点u的dist[ ]值递推各顶点的dist[ ]值时,前提是顶点u的dist[ ]值是当前最短路径长度最小的,如果图中所有边的权值都是正的,这样推导没有问题,但如果有负权值的边...
  • 最短路径算法

    2017-04-13 21:40:45
    algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。 1)算法思想原理:...
  • Bellman - Ford 算法: 一:基本算法  对于单源最短路径问题,上一篇文章中介绍了 Dijkstra 算法,但是由于... Bellman - Ford 算法可以处理路径权值为负数时的单源最短路径问题.设想可以从图中找到一个环路且这个环...
  • Bellman Ford 最短路径算法

    千次阅读 2014-06-03 09:35:32
    Dijsktra算法不能计算带负数路径的图 - 因为Dijsktra只更新当前最小路径的权值,并不会更新之后找到的新的最短路径值 - 当有负数的时候这种情况是会出现的,没有负数的情况下是不可能出现的。 而Bellman Ford是可以...
  • 1.不能处理具有负权值边的图,因为负数和一个数相加会让结果更小,那么算法就会一直执行下去。 2.如果一个图没有权值之和为负数的环存在,那么这个图还是有最短路径的。(只是不能用Dijkstra算法求了) ...
  • Floyd最短路径算法

    千次阅读 2014-09-12 13:20:29
    algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或权的最短路径问题,同时也被用于计算有向图的传递闭包。 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接...
  • 最短路径算法——Dijkstra算法——python3实现

    万次阅读 多人点赞 2018-07-03 10:28:21
    问题:根据每条边的权值,求出从起点s到其他每个顶点的最短路径最短路径的长度。 说明:不考虑权值的情况,否则会出现负值圈问题。 s:起点 v:算法当前分析处理的顶点 w:与v邻接的顶点 dvdvd_v:从s到v...
  • 有向无环图的最短路径求解算法

    千次阅读 2018-10-29 21:45:34
    对于最短路径问题,Dijkstra算法只能求解所有边的权值都是非负的加权有向图,而Bellman-Ford算法虽然可以求解有负权值边的图的最短路径,但效率并不高。对于有向无环图,下面这种基于Dijkstra和拓扑排序的算法可以在...
  • 最短路径算法—Floyd(弗洛伊德)算法

    千次阅读 2015-08-30 10:32:47
    Floyd算法(解决任意两点间的最短路径,可以正确处理有向图或负权值最短路径问题): 时间复杂度O(N3),空间复杂度O(N2); 算法思想: Floyd算法是一个经典的动态规划算法;首先我们的目标是计算顶点i到j的最短路径,...
  • 最短路径心得

    2017-08-31 08:47:00
    Dijkstra Algorithm:解决无负权边的带权有向图/无向图的单源最短路。 Bellman-Ford Algorithm:解决含负权边的带权有...(负权值回路) Dijkstra Algorithm Dijkstra算法在求解过程中,源点到集合P...
  • 一.只有五行的算法--Floyd-Warshall ...权回路指的是整个回路的权值 因为最短路径不存在,因为负数没有最小 参考啊哈算法148页 package 啊哈; import java.util.Arrays; import java...
  • 其与Dijkstra算法的区别在于Belllman Ford算法的应用范围更广,例如其可以用来处理带有权重的加权图中的最短路径问题。由于Dijkstra算法本质上是一种贪心算法,因而当图中存在路径权值之和为的环时,Dijkstra...
  • 特点弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理无向图或有向图或权(但不可存在权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。基本思想通过 Floyd 算法计算图 G=(V,{E})G=(V...
  • Bellman--Ford算法可以处理路径权值为负数的单源最短路径问题。 时间复杂度 o(n*m)  设想可以从图中找到一个环路,且这个环路中所有路径的权值之和为。那么通过这个环路,环路中任意两点的最短路径就可以无穷小...
  • 解决任意两点间最短路径的一种算法,可以正确处理有向图或权,同时也被用于有向图的传递闭包。 算法思路 计算最短路径时,需要引入两个矩阵,矩阵S中的元素a[ i ] [ j ]表示第i个顶点到第j个顶点的距离,矩阵P中的...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 163
精华内容 65
关键字:

最短路径处理负权值