Bellman-Ford——解决负权边 dijkstra算法虽然好,但是它不能解决带有负权边(边的权值为负数)的图,Bellman-Ford算法的核心代码只有4行,可以完美地解决带有负权边的图。 for(k=1;k<=n-1;k++){ for(i=1;i<=m;i++){ if(dis[v[i]]>dis[u[i]]+w[i]){//能否通过u[i]→v[i]这条边,使得1号顶点到v[i]号顶点的距离变短。即dijkstra算法中的松弛 dis[v[i]]=dis[u[i]]+w[i]; } }…

2017年9月23日 0条评论 1点热度 阅读全文

一.Dijkstra算法 如何理解Dijkstra算法 Dijkstrashi适用于权值非负的情况。 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。 问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由…

2017年8月14日 0条评论 1点热度 阅读全文

#include <iostream> #include <algorithm> #include <cstdio> #include <queue> #define CLR(a,b) memset(a,(b),sizeof a) using namespace std; const int INF = 0x3f3f3f3f; const int maxx = 1e5; struct edge{ int from,to,cost; }es[maxx]; int dis…

2017年8月13日 0条评论 1点热度 阅读全文

#include <iostream> #include <vector> using namespace std; int F,N,M,W; const int INF=1<<30; struct Edge { int s,e,w; Edge(int ss,int ee,int ww):s(ss),e(ee),w(ww) {} Edge() {} }; vector<Edge> edges; int dist[1000]; int Bellman_ford(int …

2017年8月9日 0条评论 2点热度 阅读全文

Floyd-Warshall——只有五行的算法 求任意两个点之间的最短路程。 从i号顶点到j号顶点只经过前k号顶点的最短路程,这是一种动态规划的思想。 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; n个顶点,m条边,接下来的m行每一行有3个数,顶点u,v以及他们之间的距离 l。 #include<iostrea…

2017年8月5日 0条评论 2点热度 阅读全文

适用于: 单源最短路径(从源点s到其它所有顶点v); 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图); 边权可正可负(如有负权回路输出错误提示); 差分约束系统; Bellman-Ford算法的流程如下: 给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为inf, Distant[s]为0; 以下操作循环执行至多n-1次,n为顶点数: 对于每一条边e(u,…

2017年8月2日 0条评论 2点热度 阅读全文

#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; const int maxn = 100; const int inf = 0x3f3f3f3f; int n,m; struct node { int x;int d; node…

2017年7月30日 0条评论 2点热度 阅读全文

Bellman-Ford Algorithm Dijkstra算法虽然好,但是它不能解决带负权边,Floyd-Warshall虽然简单但时间复杂度高, 而Bellman-Ford 就是那个perfect。 核心代码: for (int k=1; k<=n-1; k++) for (int i=1; i<=m; i++) if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]]=dis[u[i]]+w[i]; 上面的代码中,外循环一共循环了n-1次(n为顶点的个数),内循环循环了…

2017年7月26日 0条评论 1点热度 阅读全文

权值的概念引入: 权值就是定义的路径上面的值。 一般来说,权值愈小,路径愈佳。 Bellman-ford算法的简介: Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。 松弛: 松弛就是更新两点间的最短路径。 Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E), 其…

2017年7月23日 0条评论 2点热度 阅读全文

题目大意: 一个有向图,给你n个点,m条双向路径,以及t条虫洞。每条路径描述在两个点ab之间移动需要时间v。每条虫洞描述从a到b需要时间-v(类似于时空穿越)。现在就问你,一个人能否从某个点开始,通过若干次虫洞和路径,在他出发之前的每个时刻回到出发点。注意:两个点之间有可能有多条路径! 分析: 相当于找一个有向图中的负权回路。关于两个点之间可能有多条路径这个事情,在存图的时候要好好考虑一下。比如两个点AB之间有两条路径a,b(va>vb)以及一条虫洞单向c,那么,为了形成负权环路,我的存储方式应该是:map …

2017年4月21日 0条评论 2点热度 阅读全文