图论中的常见算法分析比较和模板
图论小结（一）
从一开始搞ACM到现在也有几个年头了，而搞图论的时间可是从一开始搞ACM开始。所以，总是对图论有着一种独有的感情。图论的内容说难不难，但是确实在算法中日常生活中可以经常遇到，且一个很有趣的算法。这也是我当初选择图论的原因，但是图论的代码量一般都比较的大，当初就是看到别人啪啪的一下只就敲出了几百行的图论代码，而自己当时是佩服的不得了啊。可是进入图论后，才发现，一照进图论十年不想敲代码啊。。。。
废话说太多了，其实图论内容很多。今天，最要总结一下最短路和生成树还有拓扑问题。还有一下更高深的网络流啊啥的一堆等下次再说。
一、最小生成树
解决最小生成树的问题，主要有两个算法。
1、Kruscal算法
2、Prime算法
Kruscal算法百度百科的解释及步骤：
求加权连通图的最小生成树的算法。kruskal算法总共选择n-
1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
空间复杂度为O（N*N）
时间复杂度为O（N*logN）(根据排序的算法时间决定)
Prim算法百度百科的步骤：
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2) Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
采用堆可以将复杂度降为O(mlog n)，如果采用Fibonacci堆可以将复杂度降为O(n log n + m)
注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。
在推荐一个生成树讲的话的博客以供大家参考学习：博客链接
int Prim()
int dis[N],ans = 0;
//生成树当前的最小花费，最终的最小花费
for(int i = 1;i <=++i){
dis[i] = graph[1][i];
for(int i = 2;i <=++i){
//N个顶点要连通只须n-1条边
int x = 1,m = INF;
for(int j = 2;j <=++j){ //根据贪心，找出当前最短的一条边
if(dis[j] != -1&&dis[j] < m)
m = dis[x = j];
dis[x] = -1;
//改点已经使用过，不可能在出现更小的情况
for(int j = 2;j
graph[x][j]))
//更新点（当前j点的最短距离，跟从x到j那个更小）
dis[j] = graph[x][j];
二、最短路算法
最短路算法最要使用的有三个Dijkstra算法和Bellman-Ford以及Floyd算法。而这三个算法有的都有自己的优化程序，下面会一一讲述。
Dijkstra算法：
这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度&#20540;被赋为 0 （d[s] = 0），若存在能直接到达的边（s,m），则把d[m]设为w（s,m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 和上述 m 外 d[v] =
∞）。当算法退出时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从
s 到 v 的路径。这条路径的长度是 d[u] &#43; w(u, v)。如果这个&#20540;比目前已知的 d[v] 的&#20540;要小，我们可以用新&#20540;来替代当前 d[v] 中的&#20540;。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 d[u] 达到它最终的&#20540;的时候每条边（u, v）都只被拓展一次。
时间复杂度我O（|V^2|）
但是可以优化到O（n*logn）优化程序可以看我以前写的文章：文章链接
function Dijkstra(G, w, s)
for each vertex v in V[G]
d[v] := infinity
// ⒏鼽c的已知最短距x先O成oF大
previous[v] := undefined
// 各点的已知最短路径上的前趋都未知
// 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
S := empty set
Q := set of all vertices
while Q is not an empty set
// Dijkstra演算法主w
u := Extract_Min(Q)
S.append(u)
for each edge outgoing from u as (u,v)
if d[v] > d[u] + w(u,v)
// 拓展边（u,v）。w(u,v)为从u到v的路径长度。
d[v] := d[u] + w(u,v)
// 更新路径长度到更小的那个和值。
previous[v] := u
现在就说说刚才在Prim算法中提到了但是没有解释的那行程序吧。
Prim更新：if(d[y] != -1&&d[y]>graph[x][y]) d[y] = graph[x][y];
//d[i]==-1表示改点已经更新过
Dijkstra更新：if(d[y]>d[x]&#43;w[x][y]) d[y] = d[x]&#43;w[x][y];
为什么会有这个区别呢?其实，只要你对这两个算法的本质理解了，你就自然会知道了。上面我们已经提到了Prim是求解最小生成树的，其终极目标是使得一个图连通且最终花费最小。而Dijkstra是求单源最短路的。即，给你一个起始点，叫你求出从这个起始点到各点或者给定目标点的最短距离。所以，我们在为Prim更新的时候考虑的是最终总的花费最小，而考虑Dijkstra是考虑起点到当前更新点的花费最小。
所以，最终我得到的d[]也是有区别的。prim的d[]是表示当前连通改点最小的花费d[]，而Dijkstra表示的是从起点到当前更新点的最小花费是d[].
vcD4KPHA+zbzL5Mi7tOrBy7Xjo6y1q8rHyLS/ydLUuty6w7XEveLKzcv7w8fBvbj2tcTH+LHwoaPG5Mq1o6zKx8/ru63O3s/yzby1xKOsvs201brP18W/tLDJoaM8L3A+CjxwPsjnufujrMrHcHJpbbXEu7DKx9Gh1PGjqDGjrDKjqSYjNDM7o6gyo6wzo6mju7b4RGlqa3N0cmG1xLuw1PLKx7j80MKjqDGjrDOjqaOovNnJ6MbwtePOqjGjqS7P1tTa06a4w9aqtcDL+8v7w8e1xMf4sfDBy7DJoaM8L3A+CjxwPjxicj4KPC9wPgo8cD5CZWxsbWFuLUZvcmTL47eozqy7+bDZv8a94srNo7o8L3A+CjxwPiAgIMv8tcTUrcDtyse21M28vfjQ0FYtMbTOy8mz2rLZ1/ejrLXDtb3L+dPQv8nE3LXE1+62zMK3vraho8bk08XT2rXPv8bLubO5y+O3qLXEt73D5srHsd+1xMioJiMyMDU0MDu/ydLUzqq4usr9oaLKtc/WvPK1paOsyLG148rHyrG85Li01NO2yLn9uN+jrLjftO9PKFZFKaGjtavL47eov8nS1L340NDI9LjJ1tbTxbuvo6zM4bjfwcvQp8LKoaM8L3A+Cgo8cD4gICAgICCxtLb7wvwtuKPM2Mvjt6jT67XPv8bLubO5y+O3qMDgJiMyMDI4NDujrLa80tTLybPastnX986qu/m0oaOsvLS5wLzGtcTX7rbMwre+tiYjMjA1NDA7vaW9pbXYsbu4/LzT17zIt7XEJiMyMDU0MDvM5rT6o6zWsdbBtcO1vdfu08W94qGj1NrBvbj2y+O3qNbQo6y8xsvjyrHDv7j2sd/WrrzktcS5wLzGvuDA6yYjMjA1NDA7tryxyNXmyrUmIzIwNTQwO7Tzo6yyosfSsbvQwtXStb3Ct762tcTX7tChs6S2yMzmtPqhowogyLu2+KOstc+/xsu5s7nL47eo0tTMsNDEt6jRocihzrSxu7SmwO21xL7f09DX7tChyKgmIzIwNTQwO7XDvdq146OsyLu687bUxuS1xLP2sd+9+NDQy8mz2rLZ1/eju7b4sbS2+8L8LbijzNjL47eovPK1pbXYttTL+dPQsd+9+NDQy8mz2rLZ1/ejrLmy"E | ? 1次，其中 |E |是图的边的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行O（|V|?|E|)次，|V|和|E|分别是节点和边的数量）。
procedure BellmanFord(list vertices, list edges, vertex source)
// 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息
// 步骤1：初始化图
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// 步骤2：重复对每一条边进行松弛操作
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// 步骤3：检查负权环
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "图包含了负权环"
改算法同样也有一个很常用的优化算法SPFA算法，就是将检查的时候常常用FIFO来代替了循环检查。
Head[]为邻接表的表头
Key[] 为邻接表的顶点
Next[]为邻接表的下个节点
为该点的权重
void SPFA(int s)
//s 为起点
int c[MAXV];
//判断是否有负环
bool inq[MAXV];
//在队列中的标记
for(int i = 0;i
d[x]+w[e]){
d[Key[e]] = d[x] + w[e];
if(!inq[Key[e]]){
//如果已经在队列中，就不要重复加了
inq[Key[e]] = 1;
c[Key[e]]++;
if(c[Key[e]] > MaxVerter)
RETURN "有负环"
q.push(Key[e]);
判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
&#65279;&#65279;
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。计算机图论中，如何在有负权环的情况下求出其他不是负无穷的路径？（好方法加分）_百度知道
计算机图论中，如何在有负权环的情况下求出其他不是负无穷的路径？（好方法加分）
计算机图论中，如何在有负权环的情况下求出其他不是负无穷的路径？（好方法加分）在一张图中给定源点，让你求各个点的最短路（有向图），假设有负权环，如何求出其他不是-无穷的最短路？
这是一道待解决的难题
您的回答被采纳后将获得系统奖励20（财富值+经验值）+难题奖励10（财富值+经验值）+提问者悬赏40（财富值+经验值）
这个有很多种方法，我想了想，最简单的可能是这么做：直接用 Bellman-Ford 算法。Bellman-Ford 一共有 n-1 次迭代（n 为顶点数），第 k 次迭代后，算出的是 &=k 条边的最短路径。如果没有负权环，那么最短路径最多有 n-1 条边，所以 n-1 次迭代就够了。如果有负权环，第 n-1 次迭代后，如果继续迭代，那么经过负权环的最短路径会在相应的时候减小。具体说，如果迭代 2n-1 次的话，那么 Bellman-Ford 算法求出的是 &=2n-1 条边的最短路径。而负权环最多有 n 条边，所以相比于 &=n-1 条边时的最短路径，&=2n-1 条边时的最短路径肯定会多经过负权环一次，所以肯定会更小。于是，我们的方法就是进行 2n-1 次迭代，看谁的最短路径比 n-1 次迭代时的小，谁就经过了负权环。
如果发现d[v[e]]的最短路径比n-1次迭代的小，我们直接就可以把它变成-无穷对吗？其他没有这种情况的点就直接输出就可以吗？
是的，就是这样。
其他类似问题
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁查看: 31|回复: 0
计算机图论中，如何在有负权环的情况下求出其他不是负无穷的路径？（好方法加分）
学雷锋不留名
学雷锋不留名&
浏览全部内容，马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
已有账号？ 或者
计算机图论中，如何在有负权环的情况下求出其他不是负无穷的路径？（好方法加分）
在一张图中给定源点，让你求各个点的最短路（有向图），假设有负权环，如何求出其他不是-无穷的最短路？
Powered by