精华内容
下载资源
问答
  • 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;
    }
    

     

    展开全文
  • 路径判,可以用强连通判断,如果缩点后连通分支数为1且该连通...最长最短路径_可以用SPFA算法:当某一点的进队次数>该点的入度个数,则路成环 _可以用SPFA算法:当某一点的进队次数>n-1时,有

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


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


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

    展开全文
  • POJ 3259 Wormholes(最短路径,求负环) 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 ...

    POJ 3259 Wormholes(最短路径,求负环)

    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..N, M (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, F. F farm descriptions follow.
    Line 1 of each farm: Three space-separated integers respectively: N, M, and W
    Lines 2.. M+1 of each farm: Three space-separated numbers ( S, E, T) 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 ( S, E, T) 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

    Http

    POJ:https://vjudge.net/problem/POJ-3259

    Source

    最短路径,求负环

    题目大意

    给出若干双向道路和单向虫洞,虫洞可以回复时间(即边权为负),而正常的双向道路需要花费一定的时间,现在求能否通过虫洞求得一个负环

    解决思路

    运用spfa算法,对每一个点做一个统计,统计入队的次数,如果发现次数>=点数,则说明有负环

    代码

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    
    const int maxN=600;
    const int inf=2147483647;
    
    class Edge
    {
    public:
        int v,w;
    };
    
    int n,m,m2;
    vector<Edge> E[maxN];
    bool inqueue[maxN];
    queue<int> Q;
    int Dist[maxN];
    int Tot[maxN];
    
    int main()
    {
        int T;
        while (cin>>T)
        {
        for (int ti=1;ti<=T;ti++)
        {
            scanf("%d%d%d",&n,&m,&m2);
            for (int i=1;i<=n;i++)
            {
                Dist[i]=inf;
                E[i].clear();
            }
            for (int i=1;i<=m;i++)
            {
                int u,w,v;
                scanf("%d%d%d",&u,&v,&w);
                E[u].push_back((Edge){v,w});
                E[v].push_back((Edge){u,w});
            }
            for (int i=1;i<=m2;i++)
            {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                E[u].push_back((Edge){v,-w});
            }
            memset(inqueue,0,sizeof(inqueue));
            memset(Tot,0,sizeof(Tot));
            while (!Q.empty())
                Q.pop();
            Dist[1]=0;
            Q.push(1);
            inqueue[1]=1;
            bool get=0;
            do
            {
                int u=Q.front();
                Q.pop();
                inqueue[u]=0;
                Tot[u]++;
                if (Tot[u]>=n)
                {
                    get=1;
                    break;
                }
                for (int i=0;i<E[u].size();i++)
                {
                    int v=E[u][i].v;
                    int w=E[u][i].w;
                    if (Dist[v]>Dist[u]+w)
                    {
                        Dist[v]=Dist[u]+w;
                        if (inqueue[v]==0)
                        {
                            Q.push(v);
                            inqueue[v]=1;
                        }
                    }
                }
            }
            while (!Q.empty());
            if (get)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/SYCstudio/p/7226467.html

    展开全文
  •  1、线性时间内解决单点最短路径问题  2、能够处理权边问题  3、能够找出最长路径 不足:因为是基于拓扑排序的,所以不能解决带的问题  import java.util.ArrayList; import java.util.Scanner; import java...

    特点:
           1、线性时间内解决单点最短路径问题
           2、能够处理负权边问题
           3、能够找出最长路径
    不足:因为是基于拓扑排序的,所以不能解决带环的问题 

    import java.util.ArrayList;
    import java.util.Scanner;
    import java.util.Stack;
    
    import Graph.HasCycle;
    
    public class TopDij {
    	static boolean[]visit;
    	static boolean[]onStack;
    	static Stack<Integer> stack;
    	static int n, m;
    	static boolean hasCycle = false;
    	static int[]dis;
    	static int INF = 99999999;
    	static ArrayList<EdgeS> []adj;
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		n = in.nextInt();
    		m = in.nextInt();
    		visit = new boolean[n+1];
    		adj = new ArrayList[n+1];
    		stack = new Stack<>();
    		dis = new int[n+1];
    		onStack = new boolean[n+1];
    		for(int i = 1; i <= n; i++ ) {
    			adj[i] = new ArrayList<>();
    		}
    		for(int i = 0; i < m; i++ ) {
    			int from = in.nextInt();
    			int to = in.nextInt();
    			int w = in.nextInt();
    			adj[from].add(new EdgeS(from, to, w));
    		}
    		bfs(1);
    //		while(!stack.isEmpty()) {
    //			System.out.println(stack.pop() + " ");
    //		}
    		if(!hasCycle) {
    			shortPath(1);
    			
    			for(int i = 1; i <= n; i++ ) {
    				System.out.println(dis[i] + " ");
    			}
    		}
    		else {
    			System.out.println("hasCycle");
    		}
    	}
    	public static void shortPath(int s) {
    		for(int i = 1; i <= n; i++ ) {
    			dis[i] = 99999999;
    		}
    		dis[s] = 0;
    		while(!stack.isEmpty()) {
    			int cur = stack.pop();
    			for(EdgeS e: adj[cur]) {
    				if(dis[e.to] > dis[cur] + e.w) {
    					dis[e.to] = dis[cur] + e.w;
    				}
    			}
    		}
    		
    	}
    	public static void bfs(int cur) {// 进行拓扑排序的同时检查是否含有环 有环的话就退出
    		visit[cur] = true;
    		onStack[cur] = true;
    		for(EdgeS e:adj[cur]) {
    			if(!visit[e.to]) {
    				bfs(e.to);
    			}
    			else if(onStack[e.to]){
    				hasCycle = true;
    				return;
    			}
    		}
    		onStack[cur] = false;
    		stack.push(cur);//记录拓扑排序结果 、逆后序
    	}
    }
    class EdgeS{
    	int from, to, w;
    	public EdgeS(int f, int t, int w) {
    		from = f;
    		to = t;
    		this.w = w;
    	}
    }

    展开全文
  • 图——单源最短路径(三)加权有向无图中的最短路径算法 在许多应用中的加权有向图都是不包含有向的,因此对于这些图可以采用一种将拓扑排序和顶点的放松结合起来的算法,该算法与Dijkstra算法之间的区别: (1...
  • 最短路径

    2015-10-10 14:12:00
    最短路 在图上求最短路径是一类非常常见的问题...求图中最短路径的方法主要有:Dijkstra算法: 求单源、无权值边最短路径BellmanFord算法:求单源、有权值边,无权值环最短路径SPFA算法:求单源、有权值边,...
  • 一、最短路径最短路径:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。求最短路径的四个算法如下:二、算法概述【Dijkstra算法】单源最短路:从单个源点出发,到所有结点的最短路作用:...
  • PS: 使用spfa时标记最短路径,借助path数组标记,path[i]表示从s->i的最短路中经过的i的父亲节点,然后输出path[]便是从t->s的最短路径,可以借助递归输出s->t,以上题为例. #include #include #include ...
  • dijkstra单源最短路径算法 ...因为存在的话就不存在最短路径 复杂度 O(ElogV) // Dijkstra算法求最短路径 template<typename Graph, typename Weight> class Dijkstra{ private: Graph &G; // ...
  • 单源最短路径

    2020-08-25 18:34:07
    如果图G包含从源节点s可以到达的权值为的的环路,则最短路径权重定义不成立(总是可以找到权值更小的路径)。 如果图G不包含那样的环路,那么即使有权边也能计算最短路径权重。 Dijkstra算法需要图所有边权都为...
  • /*寻找有负环加权有向图的最短路径,如果顶点能到达负环就不存在最短路径,这是问题转换成找负环 如果顶点不能到达负环就找能到达点的最短路径。 bellmanFordSP的relax(pq.shift(),G)不能换成relax(pq.pop(),G),...
  • 最短路径问题

    2018-03-23 10:42:03
    最短路径问题 单源最短路径非加权图的最短路径 加权图的最短路径 带有权值的图 有向无图 所有顶点对间的最短路径 单源最短路径给出一个加权图和图上的一个节点s,找出s到图中每一节点的最短路径。非加权图的最短...
  • 1、在非网图中,最短路径是指两顶点之间经历的边数最少的路径。 在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。 单源点到其他顶点的最短路径 Dijkstra方法,O(n2) 任意一对顶点之间的最短路径 ...
  • aha6最短路径

    2021-02-03 16:12:33
    aha6最短路径最短路径 Floyd-Warshall算法Dijkstra算法-单源最短路径Bellman-Ford解决权边Bellman-Ford的队列优化最短路径算法比较 最短路径 Floyd-Warshall算法 通过依次经过每个点来寻找最短路径。Floyd-...
  • Bellman-Ford算法核心代码...外循环循环n-1次(n为顶点个数),内循环循环m次(m是边的个数),也即是枚举每一条边,dis数组和Dijkstra算法一样,用来记录源点到其余各顶点的最短路径。u,v,w三个数组用来记录边的信息。
  • 只要有负环就可以在里面循环好多次,然后攒够了足够的时间就可以随便找一条路回家啦 #include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3...
  • 最短路径2

    2018-08-11 22:52:00
    在之前的博客中,我们了解到了求单源最短路径的迪杰斯特拉算法,但是需要指出的是,迪杰斯特拉算法是无法解决问题的,因为很显然的是,存在边权的有向图,随着update()操作最短路径将无限的变小。...
  • 求出从指定顶点s到其余顶点的最短路径,并判断图中是否存在负环。 例图 思路 使用dist[]数组存放每个结点距离起始点的距离,一共进行N-1次循环(因为一共有N个顶点,最多的路径也只有N-1条边),每次循环对每一条边...
  • http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2473 ...You are given a directed graph G(V,E) with a set of vertices and edges....
  • johnson最短路径

    2017-06-30 17:14:04
    Johnson算法是求稀疏图的多元最短路径的算法,权值可以为负,但是不可以有负环。Johson算法是Bellman-Ford算法, Reweighting(重赋权重)和Dijkstra算法的大综合。主要的思想是使用dijstra算法对每个结点求单源最短路...
  • 若没有负环外循环最多进行|V|-1次即可,就可得到最短路径, 那么若存在负环,则第|V|次操作还改变D数组,则有负环负环即回路中权值相加为负数。 如果陷入负环中,环中的顶点最短路径就会陷入死循环,无限变小,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 623
精华内容 249
关键字:

最短路径负环