使用Dijkstra's在加权有向图中找到最低权重周期 [英] Find the lowest-weight cycle in a weighted, directed graph using Dijkstra's

问题描述

我在为这个问题而苦苦挣扎。如下所示：

Hi I am struggling with this question. It is the following:

设计一种算法，以找到权重最低的循环（即图中所有循环，其中一个具有加权有向图G =（V，E）中最小的边缘权重之和）。简要说明运行时间和空间复杂性。假设所有边都是非负的。它应在O（| V || E | log | V |）时间运行。
提示：使用多次调用Dijkstra的算法。

Devise an algorithm to find the lowest-weight cycle(i.e. of all cycles in the graph, the one with the smallest sum of edge weights), in a weighted, directed graph G = (V,E). Briefly justify the runtime and space complexity. Assume all edges are non-negative. It should run in O(|V||E|log|V|) time. Hint: Use multiple calls to Dijkstra's algorithm.

我见过使用Floyd-Warshall的解决方案，但我想知道如何我们将使用Dijkstra以及如何在给定的时间限制内做到这一点。

I have seen solutions that use Floyd-Warshall but I was wondering how we would do this using Dijkstra's and how to do it within the time constraint given.

我有几点困惑：

• 首先，我们如何甚至知道图中有多少个周期以及
  如何检查这些周期？


• 此外，为什么| E || V | log | V |？据我了解，您应该遍历
  的所有顶点，因此使其成为| V | log | V |。

这是对于我的个人学习，因此，如果有人有可以使用的示例，那将对我有很大帮助！我并不是真正在寻找伪代码-只是一种通用算法，可以了解如何使用从一个节点到所有节点的最短路径来帮助我们解决此问题。
谢谢！

This is for my personal learning so if anyone has an example they could use, it would greatly help me! I am not really looking for pseudo-code - just a general algorithm to understand how using the shortest path from one node to all nodes is going to help us solve this problem. Thank you!

推荐答案

从每个顶点调用Dijkstra的算法，以找到到自身的最短路径（如果存在）。从任何顶点到其自身的最短路径是最小周期。
Dijkstra的算法取O（| E | log | V |），所以总时间为O（| V || E | log | V |）。

Call Dijkstra's algorithm from each vertex to find the shortest path to itself, if one exists. The shortest path from any vertex to itself is the smallest cycle. Dijkstra's algorithm takes O(|E| log |V|), so total time is O(|V||E| log |V|).

请注意，这次可能比Floyd-Warshall还要糟糕，因为图中可能有O（| V | ^ 2）条边。

Note that this time can be worse than Floyd-Warshall, because there can be O(|V|^2) edges in the graph.

这篇关于使用Dijkstra's在加权有向图中找到最低权重周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！