精华内容
下载资源
问答
  • bellman_ford最主要的功能还是求出源点到各个点的最短路径,而在它更新最短路径(就是dis[]),发现了有回环路时,直接跳出,表明这个图不能求出最短路径,所以说发现回环路只是它附带的一个产物 XD ,所以无论源点...

    Description

    While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..NM (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

    As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

    To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

    Input

    Line 1: A single integer, FF farm descriptions follow. 
    Line 1 of each farm: Three space-separated integers respectively: NM, and W 
    Lines 2..M+1 of each farm: Three space-separated numbers (SET) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path. 
    Lines M+2..M+W+1 of each farm: Three space-separated numbers (SET) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

    Output

    Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

    Sample Input

    2
    3 3 1
    1 2 2
    1 3 4
    2 3 1
    3 1 3
    3 2 1
    1 2 3
    2 3 4
    3 1 8

    Sample Output

    NO
    YES

    Hint

    For farm 1, FJ cannot travel back in time. 
    For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

    题意:

           就是让你判断是否有负环回路,

    思路:

    Bellman_ford算法

          与Dijkstra相似,Bellman-ford也可以求出单源的最短路径,但是bellman_ford比Dijkstra好的是,Bellman_ford可以判断出路径中是否有负回环路。

          Dijkstra最重要的一步就是松弛操作,应为Dijkstra处理的数据都是正数,所以它的松弛操作是有极限的,但如果遇到负的回环路,它的松弛可以无限松弛下去,那么Bellman_ford最经典的操作来了,它把Dijkstra的松弛定个极限,当跳出这个极限后,如果还会出现可以松弛的情况,那么就是存在负回环路。

    Bellman_ford的松弛类似dp前面的松弛结果可能对后面的松弛有影响,值得注意

    判断是否有负环形路时,初始的s值为1即可,不用循环

    bellman_ford最主要的功能还是求出源点到各个点的最短路径,而在它更新最短路径(就是dis[]),发现了有负回环路时,直接跳出,表明这个图不能求出最短路径,所以说发现负回环路只是它附带的一个产物 XD ,所以无论源点s为何值都可以发现这个负回环路

    #include <iostream>
    #include <vector>
    #include <string.h>
    using namespace std;
    struct ac{
        int s, e, dis;
        ac() {}
        ac (int &_s, int &_e, int &_dis) {
            s = _s; e = _e; dis = _dis;
        }
    };
    vector<ac> vv;
    int n, m, w;
    const int INF = 0x3f3f3f3f;
    int dis[505];
    bool belmanford(int s) {
        memset(dis, INF, sizeof(dis));//初始化dis全为INF
        dis[s] = 0;//把起始点赋值为0
        for (int i = 1; i <= n; i ++) {//从第一个点到最后一个点Dijkstra最多松弛n次
            bool flag = false;//初始化默认不能在松弛了
            for (int j = 0; j < vv.size(); j ++) {//把每个边都看能否进行松弛,类似Dijkstra把关联的路径松弛
                int ss = vv[j].s;
                int ee = vv[j].e;
                int diss = vv[j].dis;
                if (dis[ee] > dis[ss] + diss) {
                    dis[ee] = dis[ss] + diss;
                    flag = true;//能松弛变成true
                }
            }
            if (!flag)//如果经过上面松弛发现全都不能在松弛了,那么Dijkstra 已经走完,直接break
                break;
        }
        for (int j = 0; j < vv.size(); j ++) {//如果上面不是通过flag退出循环的,那么就再松弛一次,如果能松弛那么表示有负回环路
            int ss = vv[j].s;
            int ee = vv[j].e;
            int diss = vv[j].dis;
            if (dis[ee] > dis[ss] + diss) {
                dis[ee] = dis[ss] + diss;
                return true;//有负回环路返回true
            }
        }
        return false;
    }
    int main() {
        int T;
        cin >> T;
        while(T--) {
            vv.clear();
            cin >> n >> m >> w;
            for (int i = 0; i < m; i ++){
                int s, e, dis;
                cin >> s >> e >> dis;
                vv.push_back(ac(s, e, dis));
                vv.push_back(ac(e, s, dis));
            }
            for (int i = 0; i < w; i ++) {
                int s, e, dis;
                cin >> s >> e >> dis;
                dis *= (-1);
                vv.push_back(ac(s, e, dis));
            }
            int f = 0;
            for (int i = 1; i <= n; i ++) {
                if (belmanford(i)) {
                    f = 1;
                    break;
                }
            }
            if (f)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        return 0;
    }
    

     

    SPFA算法

         SPFA的思想与Bellman_ford相同,都是模拟了Dijkstra松弛的操作,因为每个点最多松弛n次如果发现有点松弛了超过n次那么肯定存在负环回路

    #include <iostream>
    #include <vector>
    #include <string.h>
    #include <queue>
    using namespace std;
    struct ac{
        int e, dis;
        ac() {}
        ac (int &_e, int &_dis) {
            e = _e; dis = _dis;
        }
    };
    vector<ac> vv[305];
    int n, m, w;
    const int INF = 0x3f3f3f3f;
    int dis[505];
    int c[305], vis[305];
    bool SPFA(int s) {
        queue<int> q;
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;//起始点
        memset(vis, 0, sizeof(vis));//全赋初值
        memset(c, 0, sizeof(c));
        q.push(s);
        vis[s] = 1;//如队列就标记
        c[s] = 1;//记录次数
        while(!q.empty()) {
            int x;
            x = q.front(); q.pop();//队列头拿出
            vis[x] = 0;//取消标记
            for (int j = 0; j < vv[x].size(); j ++) {//松弛相关点
                ac t = vv[x][j];
                if (dis[t.e] > dis[x] + t.dis) {
                    dis[t.e] = dis[x] + t.dis;
                    if (!vis[t.e]) {//如果此时这个点不在队列中,如队
                        vis[t.e] = 1;//并标记
                        c[t.e] ++;//次数++
                        q.push(t.e);//如对
                        if (c[t.e] > n) {//如果发现大于n次了,返回true
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
    int main() {
        int T;
        cin >> T;
        while(T--) {
            for (int i = 1; i < 305; i  ++) {
                vv[i].clear();
            }
            cin >> n >> m >> w;
            for (int i = 0; i < m; i ++){
                int s, e, dis;
                cin >> s >> e >> dis;
                vv[s].push_back(ac(e, dis));
                vv[e].push_back(ac(s, dis));
            }
            for (int i = 0; i < w; i ++) {
                int s, e, dis;
                cin >> s >> e >> dis;
                dis *= (-1);
                vv[s].push_back(ac(e, dis));
            }
            int f = 0;
            if (SPFA(1))
                f = 1;
    
            if (f)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
        return 0;
    }
    

     

    展开全文
  • 如果从一个点沿着某条路径出发,又回到了自己,而且所经过的边上的权和小于0,就说这条路是一个权回路。 如果存在权回路,只输出一行 −1; 如果不存在权回路,再求出一个点 S 到每个点的最短路的长度。 约定:...

    一、题目描述

    输入数据给出一个有 N 个节点,M 条边的带权有向图。

    要求你写一个程序,判断这个有向图中是否存在负权回路。

    如果从一个点沿着某条路径出发,又回到了自己,而且所经过的边上的权和小于0,就说这条路是一个负权回路。

    • 如果存在负权回路,只输出一行 −1;
    • 如果不存在负权回路,再求出一个点 S 到每个点的最短路的长度。
    • 约定: S 到 S 的距离为 0,如果 S 与这个点不连通, 则输出NoPath。

    输入格式

    • 第一行三个正整数,分别为点数 N,边数 M,源点 S;

    • 以下 M 行,每行三个整数 a,b,c,表示点 a,b 之间连有一条边,权值为 c。

    • 图中点的编号从 1 到 N。

    输出格式

    • 如果存在负权环,只输出一行 −1,否则按以下格式输出:
    • 共 N 行,第 i 行描述 S 点到点 i 的最短路:
    • 如果 S 与 i 不连通,输出 NoPath;
    • 如果 i=S,输出 0。
    • 其他情况输出 S 到 i 的最短路的长度。

    数据范围

    • 2≤N≤1000,
      1≤M≤105,
      1≤a,b,S≤N,
      |c|≤106
    输入样例:
    6 8 1
    1 3 4
    1 2 6
    3 4 -7
    6 4 2
    2 4 5
    3 6 3
    4 5 1
    3 5 4
    输出样例:
    0
    6
    4
    -3
    -2
    7
    

    二、题解

    方法一:SPFA

    先让所有点作为起点,判断一下是否有负环:

    • 如果没有,则继续以起点 S 跑一边 spfa。
    • 有则输出 -1 结束战斗。

    最后的样例错误:不知何原因。

    import java.util.*;
    import java.math.*;
    import java.io.*;
    public class Main{
    	static int V, E;
    	static int INF = 0x3f3f3f3f;
    	static int MAXN = (int)1e5 + 50;
    	static Edge[] edges;
    	static int[] dist, count, head;
    	static int tot;
    	static boolean[] inq;
    	static void addEdge(int u, int v, int w) {
    		edges[++tot] = new Edge();
    		edges[tot].to = v;
    		edges[tot].w = w;
    		edges[tot].next = head[u];
    		head[u] = tot;
    	}
    	static boolean spfa(int S) {
    	    inq = new boolean[MAXN];
    		count = new int[MAXN];
    		dist = new int[MAXN];
    		Arrays.fill(dist, INF);
    		dist[S] = 0;
    		Queue<Integer> q = new ArrayDeque<>();
    		q.add(S);
    		inq[S] = true;
    		
    		while (!q.isEmpty()) {
    			int v = q.poll();
    			inq[v] = false;
    			for (int i = head[v]; i != 0; i = edges[i].next) {
    				int to = edges[i].to, w  = edges[i].w;
    				if (dist[to] > dist[v] + edges[i].w) {
    					count[to] = count[i] + 1;
    					if (count[to] > V)
    						return true;
    					dist[to] = dist[v] + edges[i].w;
    					if (!inq[to]) {
    					    q.add(to);
    					    inq[to] = true;
    					}
    				}
    			}
    		}
    		return false;
    	}
        public static void main(String[] args) throws IOException {  
            Scanner sc = new Scanner(new BufferedInputStream(System.in));
            BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
            
    		V = sc.nextInt();
    		E = sc.nextInt();
    		int S = sc.nextInt();
    		inq = new boolean[MAXN];
    		count = new int[MAXN];
    		dist = new int[MAXN];
    		edges = new Edge[MAXN];
    		head = new int[MAXN];
    		
    		for (int i = 1; i <= E; i++) {
    			int a = sc.nextInt();
    			int b = sc.nextInt();
    			int c = sc.nextInt();
    			addEdge(a, b, c);
    		}
    		for (int i = 1; i <= V; i++) {	//bug01
    		    if (spfa(i))  {
    		        System.out.println(-1);
    		        return;
    		    }
    		}
    		boolean res = spfa(S);
    		if (res)  {System.out.println(-1);return;}
    		for (int i = 1; i <= V; i++) {
    			if (dist[i] == INF)
    			    System.out.println("NoPath");
    		    else 
    			    System.out.println(dist[i]);
    		}
        }
    	static class Edge {
    		int to, w, next;
    		Edge() {}
    		Edge(int to, int w, int next) {
    			this.to = to;
    			this.w = w;
    			this.next = next;
    		}
    	} 
    }
    

    复杂度分析

    • 时间复杂度: O ( E ) O(E) O(E)
    • 空间复杂度: O ( E + V ) O(E+V) O(E+V)

    方法二:spfa + List

    上面的尝试,我们发现几个 bug,我们虽然说是以每个点为起点跑了一篇 spfa,但是他们是各自跑的,并非全部加到队列里一起跑

    存在的疑惑:

    • Q1:但是这样做,样例为什么可以过呢?
      A1:
    • Q2:请问为什么要以所有点作为起点跑一边呢?判负环跑一个点不行吗?
      A2:因为图不保证连通,有可能存在有负环,但图不连通。
    import java.util.*;
    import java.math.*;
    import java.io.*;
    public class Main{
        static int V, E;
        static int INF = 0x3f3f3f3f;
        static int MAXN = (int)1e5 + 50;
        static Edge[] edges;
        static int[] dist, count, head;
        static int tot;
        static boolean[] inq;
        static void addEdge(int u, int v, int w) {
            edges[++tot] = new Edge();
            edges[tot].to = v;
            edges[tot].w = w;
            edges[tot].next = head[u];
            head[u] = tot;
        }
        static boolean spfa( List<Integer> list) {
            inq = new boolean[MAXN];
            count = new int[MAXN];
            dist = new int[MAXN];
            Arrays.fill(dist, INF);
            
            Queue<Integer> q = new ArrayDeque<>();
            for (int i = 0; i < list.size(); i++) {
                  q.add(list.get(i));
                  inq[list.get(i)] = true;
                  dist[list.get(i)] = 0;
                  count[list.get(i)] = 1;
            }
            
            while (!q.isEmpty()) {
                int v = q.poll();
                inq[v] = false;
                for (int i = head[v]; i != 0; i = edges[i].next) {
                    int to = edges[i].to, w = edges[i].w;
                    if (dist[to] > dist[v] + w) {
                        count[to] = count[v] + 1;
                        if (count[to] > V)
                            return true;
                        dist[to] = dist[v] + w;
                        if (!inq[to]) {
                            q.add(to);
                            inq[to] = true;
                        }
                    }
                }
            }
            return false;
        }
        public static void main(String[] args) throws IOException {  
            Scanner sc = new Scanner(new BufferedInputStream(System.in));
            BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
    
            V = sc.nextInt();
            E = sc.nextInt();
            int S = sc.nextInt();
            edges = new Edge[MAXN];
            head = new int[MAXN];
    
            for (int i = 1; i <= E; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                addEdge(a, b, c);
            }
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i <= V; i++) {
                list.add(i);
            }
            if (spfa(list)){
                System.out.println(-1);
                return; 
            }
            list = new ArrayList<>();
            list.add(S);
            spfa(list);
            for (int i = 1; i <= V; i++) {
                if (dist[i] == INF)
                    System.out.println("NoPath");
                else 
                    System.out.println(dist[i]);
            }
        }
        static class Edge {
            int to, w, next;
            Edge() {}
        } 
    }
    

    get 到的技能:

    • 所有点一起进队列跑出来的效果和一个一个跑是一样的。
    • 需要注意题目有没有明确图是连通的。
    展开全文
  • 路径判,可以用强连通判断,如果缩点后连通分支数为1且该连通...最长最短路径_可以用SPFA算法:当某一点的进队次数>该点的入度个数,则路成环 _可以用SPFA算法:当某一点的进队次数>n-1时,有

    路径判环,可以用强连通判断,如果缩点后连通分支数为1且该连通分支的节点个数==图中节点n,则路径为强连通图


    最长最短路径判环_可以用SPFA算法:当某一点的进队次数>该点的入度个数,则路成环


    负权环_可以用SPFA算法:当某一点的进队次数>n-1时,有负权环

    展开全文
  • 单源最短路径

    2012-11-02 17:47:43
    单源最短路径C语言实现,简单易懂,适合算法学习
  • b.Floyd算法 多源,基于动态规划,本质上是一个三维的DP, 与其他算法不同,floyd是一个多源最短路径算法,即经过 一次floyd后能求出任意两点间的最短路径 c.Dijkstra 单源,只适用于**无边权**的图, 可以包含 d....

    1.简介

    动态规划Dynamic Programming: 这里的“Programming”并非指编写程序代码,而是指一种表格计算法(A tabular method),即基于表格查询的方法计算得到最优结果。

    动态规划与分治法(The Divide-and-Conquer Method)有些类似,也是将问题分解为多个子问题,并且基于子问题的结果获得最终解。二者的区别是,分治法将初始问题划分为多个不关联(Disjoint)的子问题(Subproblem)(即子问题相互之间互不依赖),递归地解决子问题,然后将子问题的解合并得到初始问题的解。与之相反,动态规划法分解得到的子问题是相互重叠的(Overlap),即子问题依赖于子子问题(Subsubproblem),子子问题又进一步依赖于下一级的子子问题,这样不断循环直至抵达不需分解的初始条件。在求解过程中,为了避免重复计算子子问题从而提高算法效率,需要将一系列子子问题的解保存到一张表中(table,C++编程一般使用std::array、std::vector或std::list实现),这也就是动态规划又被称为查表计算法的原因。

    动态规划一般应用于最优化问题(Optimization Problems)。这类问题一般存在多个解,每个解都具有一个度量值,我们期望得到具有度量值最优(即取最大或最小值)的解。该最优解一般称为最优化问题的一个解。注意,这个解并非唯一,因为最优化问题可能存在多个最优解。

    2.如何理解DP

    2.1 举例说明,通俗易懂

    先来看看生活中经常遇到的事吧——假设您是个土豪,身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w,需要用到尽量少的钞票。

    依据生活经验,我们显然可以采取这样的策略:能用100的就尽量用100的,否则尽量用50的……依次类推。在这种策略下,666=6×100+1×50+1×10+1×5+1×1,共使用了10张钞票。

    这种策略称为“贪心”:假设我们面对的局面是“需要凑出w”,贪心策略会尽快让w变得更小。能让w少100就尽量让它少100,这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明,贪心策略是正确的。

    但是,如果我们换一组钞票的面值,贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11,那么我们在凑出15的时候,贪心策略会出错:
    15=1×11+4×1 (贪心策略使用了5张钞票)
    15=3×5 (正确的策略,只用3张钞票)
    为什么会这样呢?贪心策略错在了哪里?

    鼠目寸光。
    刚刚已经说过,贪心策略的纲领是:“尽量使接下来面对的w更小”。这样,贪心策略在w=15的局面时,会优先使用11来把w降到4;但是在这个问题中,凑出4的代价是很高的,必须使用4×1。如果使用了5,w会降为10,虽然没有4那么小,但是凑出10只需要两张5元。
    在这里我们发现,贪心是一种只考虑眼前情况的策略。

    那么,现在我们怎样才能避免鼠目寸光呢?

    如果直接暴力枚举凑出w的方案,明显复杂度过高。太多种方法可以凑出w了,枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

    重新分析刚刚的例子。w=15时,我们如果取11,接下来就面对w=4的情况;如果取5,则接下来面对w=10的情况。我们发现这些问题都有相同的形式:“给定w,凑出w所用的最少钞票是多少张?”接下来,我们用f(n)来表示“凑出n所需的最少钞票数量”。
    那么,如果我们取了11,最后的代价(用掉的钞票总数)是多少呢?
    明显 什么是动态规划(Dynamic Programming)?动态规划的意义是什么? ,它的意义是:利用11来凑出15,付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
    依次类推,马上可以知道:如果我们用5来凑出15,cost就算f(10) = 2+1=3.

    那么,现在w=15的时候,我们该取那种钞票呢?当然是各种方案中,cost值最低的那一个!
    在这里插入图片描述
    显而易见,cost值最低的是取5的方案。我们通过上面三个式子,做出了正确的决策!
    这给了我们一个至关重要的启示:

    在这里插入图片描述

    这个式子是非常激动人心的。我们要求出f(n),只需要求出几个更小的f值;既然如此,我们从小到大把所有的f(i)求出来不就好了?注意一下边界情况即可。代码如下:
    在这里插入图片描述
    在这里插入图片描述
    这两个事实,保证了我们做法的正确性。它比起贪心策略,会分别算出取1、5、11的代价,从而做出一个正确决策,这样就避免掉了“鼠目寸光”!

    它与暴力的区别在哪里?我们的暴力枚举了“使用的硬币”,然而这属于冗余信息。我们要的是答案,根本不关心这个答案是怎么凑出来的。譬如,要求出f(15),只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).

    我们能这样能这样做,主要取决于问题的性质:求出f(n),只需要知道几个更小的f©。我们将求解f©称作求解f(n)的“子问题”。

    这就是DP(动态规划,dynamic programming):将一个问题拆成几个子问题,分别求解这些子问题,即可推断出大问题的解。

    2.2 如何理解DP的几个重要性质

    【无后效性】

    一旦f(n)确定,“我们如何凑出f(n)”就再也用不着了。
    要求出f(15),只需要知道f(14),f(10),f(4)的值,而f(14),f(10),f(4)是如何算出来的,对之后的问题没有影响。
    “未来与过去无关”, 这就是 无后效性 。
    (严格定义:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。)

    【最优子结构】

    回顾我们对f(n)的定义:我们记“凑出n所需的最少钞票数量”为f(n).
    f(n)的定义就已经蕴含了“最优”。 利用w=14,10,4的 最优 解,我们即可算出w=15的 最优 解。
    大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”。

    2.3 如何判断一个问题能否使用DP解决呢?

    能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。 
    
    【DP的操作过程】

    一言以蔽之:大事化小,小事化了。

    将一个大问题转化成几个小问题;
    求解小问题;
    推出大问题的解。

    【如何设计DP算法】

    下面介绍比较通用的设计DP算法的步骤。

    首先,把我们面对的局面表示为x。这一步称为设计状态。
    对于状态x,记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).
    找出f(x)与哪些局面有关(记为p),写出一个式子(称为状态转移方程),通过f(p)来推出f(x). 
    

    2.4 DP的典型应用:DAG最短路

    有向无环图DAG(Directed acyclic graph): 如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图。

    求图中节点的单源最短路径可以使用Dijkstra,BellmanFord, 算法,而对于有向无环图DAG来说,可以通过简单的动态规划来进行求解。 DAG的独特之处是所有节点可以线性化(拓扑序列),使得所有边保持从左到右的方向.

    问题很简单:给定一个城市的地图,所有的道路都是单行道,而且不会构成环。每条道路都有过路费,问您从S点到T点花费的最少费用。

    边上的数字表示过路费。
    边上的数字表示过路费。

    这个问题能用DP解决吗?我们先试着记从S到P的最少费用为fp
    想要到T,要么经过C,要么经过D。从而
    在这里插入图片描述
    好像看起来可以DP。现在我们检验刚刚那两个性质:

    • 无后效性:对于点P,一旦f§确定,以后就只关心fp的值,不关心怎么去的。
    • 最优子结构:对于P,我们当然只关心到P的最小费用,即fp。如果我们从S走到T是:
      在这里插入图片描述
      那肯定S走到Q的最优路径是:
      在这里插入图片描述
      对一条最优 的路径而言,从S走到 沿途上所有的点(子问题) 的最优路径,都是这条大路的一部分。这个问题的最优子结构性质是显然的。

    既然这两个性质都满足,那么本题可以DP。 式子明显为:
    在这里插入图片描述

    2.5 扩展:最短路径算法

    a.单源最短路径

    从一个点出发,到达其他顶点的最短路径的长度。
    基本操作:**松弛**
    d[u]+map[u, v]< d[v]这样的边(u,v)称为紧的(tense),可以对它进行松弛(relax):
    d[v] = d[u]+w, pred[v] = u
    最开始给每一个点一个很大的d值,从d[s]=0开始,不断的对可以松弛的点进行松弛,不能松弛的时候就已经求出了最短路了
    

    在这里插入图片描述

    b.Floyd算法

    多源,基于动态规划,本质上是一个三维的DP, 与其他算法不同,floyd是一个多源最短路径算法,即经过 一次floyd后能求出任意两点间的最短路径
    

    c.Dijkstra

    单源,只适用于**无负边权**的图, 可以包含环
    

    d. Bellman-ford算法

    单源,基于动态规划, 边权可正可负, 可以包含环, 可以用来判负环
    

    3. DP在Apollo项目规划模块中的应用

    Apollo项目Planning模块的EMPlanner中使用动态规划生成代价(Cost)最小的多项式路径(DP路径,见Apollo项目中的DPRoadGraph类)和速度(DP速度,见Apollo项目中的DpStGraph类),DP路径算法和DP速度算法的示意性描述如下图所示
    在这里插入图片描述
    在这里插入图片描述
    DP路径算法的基本思路是,基于给定的一条中心路径(称为参考线,ReferenceLine)和车道边界条件,每隔一定间隔的纵向距离(称为不同级(Level)上的s值)对道路截面进行均匀采样(与中心点的横向偏移值称为为l值),这样会得到图中黑点所示的采样点(这些采样点称为航点,Waypoint)数组。基于一定的规则,可以给出各航点迁移的代价值(Cost)。航点迁移不一定需要逐级进行,可以从第一级跳到第三级甚至终点,只要迁移代价值最小化即可,这显然满足动态规划的求解思路。

    DP速度算法的基本思路是,在DP路径算法生成一条可行驶的路径后,从起点开始,考虑避开路径中的所有障碍物,并且让加减速最为平顺,以最优的速度曲线(即t-s平面中的绿色曲线)安全抵达终点,这也可以使用动态规划的思路求解。

    参考文献:
    算法-最短路径:DAG、Dijkstra、Bellman-Ford
    什么是动态规划(Dynamic Programming)?动态规划的意义是什么?
    动态规划及其在Apollo项目Planning模块的应用

    展开全文
  • 1 当这张图存在时是无法算出最短路径的,也可以用Bellman-Ford算法判断这张图是否有。 2 Bellman-Ford算法一般处理的是有向图,因为如果是无向图,那么如果存在一条权边,就会构成了 ...
  • 原文地址:http://www.wutianqi.com/?p=1912 相关文章: 1.Dijkstra算法: ... 2.Floyd算法: ... Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为
  • 如果一个图出现了负环,则会导致恶性循环,会导致dis[u]出现负无穷,永远也求解不出来,但如果从源点出发,无法到达负环,则最短路径的求解不会收到影响(不在负环上的dis[u]可以求出确切值,在负环上的点v,标记dis...
  • 最短路径问题

    2021-01-12 20:37:24
    最短路径问题 系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助...
  •  1、线性时间内解决单点最短路径问题  2、能够处理权边问题  3、能够找出最长路径 不足:因为是基于拓扑排序的,所以不能解决带的问题  import java.util.ArrayList; import java.util.Scanner; import java...
  • 最短路径 最短路径算法 Dijkstra (迪杰斯特拉算法) Dijkstra –思路 Dijkstra – 执行过程 Dijkstra –代码实现 Bellman-Ford (贝尔曼-福特算法) Bellman-Ford–思路 Bellman-Ford–思考 Bellman...
  • 有向无图的最短路径

    千次阅读 2016-12-13 15:54:29
    给定一个有向无图(DAG)和一个源点,求从该源点到其他所有的顶点的最短路径。如果是无权(即权值为),可以用djistra算法完成。但如果存在权,则不行。同时,djistra算法效率并不高,既然是有向无图(DAG...
  • 而本节中所介绍的线性规划则是一种特例,可被归类在单源最短路径问题中。并可调用Bellman_Ford算法解决该问题。 在此之前,先介绍何为线性规划。 线性规划:在一般的线性规划中,对于不等式Ax ≤ b,我们给定的常量...
  • 对于一个带负权值边的有向图,实现Bellman-Ford算法,求出从指定顶点s到其余顶点的最短路径,并判断图中是否存在负环。 Bellman-Ford算法的基本思路 对图中的边进行V-1轮操作(为什么是V-1轮?除了起始点,就只有V-1...
  • 最短路径四大算法

    万次阅读 多人点赞 2017-08-19 10:14:22
    bellman-ford可以用于边权为负的图中,图里有负环也可以,如果有负环,算法会检测出负环。 时间复杂度O(VE); dijkstra只能用于边权都为正的图中。 时间复杂度O(n2); spfa是个bellman-ford的优化算法,本质...
  • 图——单源最短路径(三)加权有向无图中的最短路径算法 在许多应用中的加权有向图都是不包含有向的,因此对于这些图可以采用一种将拓扑排序和顶点的放松结合起来的算法,该算法与Dijkstra算法之间的区别: (1...
  • 一、最短路径简介        所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为...
  • 2018-03-13 17:08:57 ...理由也很简单,每次dijkstra都是将目前的额最短路添加到集合中,这也就保证了,下一次的最短路径是肯定要长于之前添加进去的最短路径的,然而在有权边的时候,这个推论...
  • 有向无图的最短路径求解算法

    千次阅读 2018-10-29 21:45:34
    对于有向无图,下面这种基于Dijkstra和拓扑排序的算法可以在线性时间内解决单点最短路径问题,且能够处理权重的边,甚至能够求出最长路径。 该算法的思想很简单:按照拓扑顺序放松顶点。因为每条边v→w都只会被...
  • 总括 在我们不知道图的类型(有圈无圈、有圈无圈)的时候, Ford算法和上文中Dijkstra算法的优化版会给予我们一种通用的解法, 但是我们要注意到他们的时间复杂度为0(E * V);...说到无圈图的最短路径, 和
  • 求解两点间最短路径的算法

    千次阅读 2020-07-19 23:42:40
    最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的对比 最短路径算法 单源最短路算法:已知...
  • 最短路径算法

    2019-06-05 16:28:48
    一、最短路径问题介绍 1、问题解释:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 2、解决问题的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) ...
  • C++解决最短路径问题

    2021-11-10 10:47:21
    先说多源最短路径算法 1.floyd算法(暴力n3): 核心代码只有三行,文字描述就是:假设n个点,点与点间有m条边(无独立的点),我们要求每个点到到其他n-1个点的最短路径,首先就是用邻接矩阵进行存图,初始化INF...
  • 1、在非网图中,最短路径是指两顶点之间经历的边数最少的路径。 在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。 单源点到其他顶点的最短路径 Dijkstra方法,O(n2) 任意一对顶点之间的最短路径 ...
  • 求出从指定顶点s到其余顶点的最短路径,并判断图中是否存在负环。 例图 思路 使用dist[]数组存放每个结点距离起始点的距离,一共进行N-1次循环(因为一共有N个顶点,最多的路径也只有N-1条边),每次循环对每一条边...
  • 它解决一般情况下的单源最短路径问题,允许边的权重为负值。同时对于给定的有向图G=(V, E)和权重函数w:E→R,它返回一个判断在路径中是否存在权重为负值的环路的布尔值。 Bellman_Ford(G, w, s) Initialize_...
  • 通过对于Djkstra的学习,大致了解了最短路径问题,但是Djsktra算法由于其操作过程上的不足,不能处理带有权边的情况,这个算法,Bellman-Ford【这些名字应该怎么记。。】则可以处理带有权的问题,其中也用到了...
  • ​ 在一无的图中,给定起点startVertex和重点endVertex,求两点之间最短路径path的长度length。 大致思路 在此之前,我们已经学会了使用Dijkstra算法(一种贪心算法)来解决最短路径问题,然而在动态规划的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,211
精华内容 3,284
关键字:

最短路径负环