图 - 如何找到最小定向周期（最小总重量）？ [英] graph - How to find Minimum Directed Cycle (minimum total weight)?

问题描述

这是一个消费税：

让G是n个顶点和m个边的加权有向图，其中所有边都具有正重量。定向循环是在相同顶点开始和结束并且包含至少一个边缘的有向路径。给出一个O（n ^ 3）算法，找到最小总重量为G的定向循环。将给出O（（n ^ 2）* m）算法的部分信用。

---

这是我的算法。

我做一个 DFS 。每当我找到一个后边缘，我知道我有一个定向循环。

然后我将沿着父数组暂时退回（直到我遍历周期中的所有顶点）计算总权重。

然后我将这个周期的总重量与 min 。 min 总是取最小总重量。在DFS完成之后，我们也会发现我们的最小定向周期。

---

那么关于时间复杂度。 >

说实话，我不知道我的算法的时间复杂度。

对于DFS，遍历采用O（m + n）（如果m是边数，n是顶点数）。对于每个顶点，它可能会指向其祖先之一，从而形成一个循环。当找到一个周期时，需要O（n）来总结总权重。

所以我认为总时间是O（m + n * n）。但是显然这是错误的，如消费者所说，最佳时间是O（n ^ 3），正常时间是O（m * n ^ 2）。

---

任何人都可以帮助我：

1. 我的算法是否正确？


2. 如果我的算法正确，那么时间复杂度是多少？


3. 这个问题有更好的算法吗？

解决方案

您可以使用 Floyd-Warshall 算法这里。

Floyd-Warshall算法找到最短路径

该算法非常简单，超过所有对（u，v） 和找到最小化$ code dist（u，v）+ dist（v，u） 的对，因为这对指示从 u 到 u 的循环，重量 dist（u，v）+ dist（v，u）。如果图形还允许自循环（边缘（u，u）），您还需要单独检查它们，因为这些循环（而且只有它们）不是通过算法检查。

伪代码

 在图上运行Floyd Warshall 
 min < -  infinity 
顶点<  - 无
对于每对顶点u，v 
 if（dist（u， v）+ dist（v，u）< min）：
 min < -  dist（u，v）+ dist（v，u）
 pair < - （u，v）
返回路径（u，v）+路径（v，u）
  

path（u，v）+ path（v，u）实际上是从u到v，然后从v到u的路径，这是一个循环。

算法运行时间为 O（n ^ 3），因为floyd-warshall是瓶颈，因为循环需要

Here is an excise:

Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n^3) algorithm to find a directed cycle in G of minimum total weight. Partial credit will be given for an O((n^2)*m) algorithm.

---

Here is my algorithm.

I do a DFS. Each time when I find a back edge, I know I've got a directed cycle.

Then I will temporarily go backwards along the parent array (until I travel through all vertices in the cycle) and calculate the total weights.

Then I compare the total weight of this cycle with min. min always takes the minimum total weights. After the DFS finishes, our minimum directed cycle is also found.

---

Ok, then about the time complexity.

To be honest, I don't know the time complexity of my algorithm.

For DFS, the traversal takes O(m+n) (if m is the number of edges, and n is the number of vertices). For each vertex, it might point back to one of its ancestors and thus forms a cycle. When a cycle is found, it takes O(n) to summarise the total weights.

So I think the total time is O(m+n*n). But obviously it is wrong, as stated in the excise the optimal time is O(n^3) and the normal time is O(m*n^2).

---

Can anyone help me with:

1. Is my algorithm correct?
2. What is the time complexity if my algorithm is correct?
3. Is there any better algorithm for this problem?

解决方案

You can use Floyd-Warshall algorithm here.

The Floyd-Warshall algorithm finds shortest path between all pairs of vertices.

The algorithm is then very simple, go over all pairs (u,v), and find the pair that minimized dist(u,v)+dist(v,u), since this pair indicates on a cycle from u to u with weight dist(u,v)+dist(v,u). If the graph also allows self-loops (an edge (u,u)) , you will also need to check them alone, because those cycles (and only them) were not checked by the algorithm.

pseudo code:

run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

path(u,v) + path(v,u) is actually the path found from u to v and then from v to u, which is a cycle.

The algorithm run time is O(n^3), since floyd-warshall is the bottle neck, since the loop takes O(n^2) time.

I think correctness in here is trivial, but let me know if you disagree with me and I'll try to explain it better.

这篇关于图 - 如何找到最小定向周期（最小总重量）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！