Floyd-Warshall和矩阵乘法图算法有什么区别? [英] What is the difference between Floyd-Warshall and matrix multiplication graph algorithms?

问题描述

我必须解决以下问题:编写一个程序，给定一个包含成本和两个顶点的有向图，找到给定顶点之间的最低成本走动，或者在图中存在负成本周期时显示一条消息.该程序应使用矩阵乘法算法.

I have to solve the following problem: Write a program that, given a directed graph with costs and two vertices, finds a lowest cost walk between the given vertices, or prints a message if there are negative cost cycles in the graph. The program shall use the matrix multiplication algorithm.

我实现了定义的矩阵乘法算法:伪矩阵乘法，其中加法运算被最小化和加法运算相乘.但是通过这样做，我最终得到了Floyd-Warshall算法.而且，我不能轻易地以此方式确定负成本周期的存在.

I implemented the matrix multiplication algorithm as it is defined: a pseudo-matrix multiplication, where addition is replaced by minimization and multiplication with addition. But by doing this, I ended up with the Floyd-Warshall algorithm Also, I can't easily determine the existence of a negative-cost cycle this way.

我认为我的算法与真实矩阵乘法图算法之间存在主要差异，但这到底是什么?

I assume there is a major difference between my algorithm, and the real matrix multiplication graph algorithm, but what is that exactly?

推荐答案

1. 您可以使用Floyd-Warshall确定负周期的存在:

https://en.wikipedia.org/wiki/Floyd ％E2％80％93Warshall_algorithm#Behavior_with_negative_cycles

尽管如此，如果存在负周期，则弗洛伊德–沃歇尔(Floyd–Warshall) 可以使用算法来检测它们.直觉如下:

Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them. The intuition is as follows:

• Floyd–Warshall算法迭代地修改所有对顶点(i，j)之间的路径长度，包括其中i = j；
• 最初，路径(i，i)的长度为零；
• 仅当路径[i，k，...，i]的长度小于零(即表示负循环)时，才能对此进行改善.
• 因此，在算法之后，如果存在从i到i的负长度路径，则(i，i)将为负.

• The Floyd–Warshall algorithm iteratively revises path lengths between all pairs of vertices (i,j), including where i=j;
• Initially, the length of the path (i,i) is zero;
• A path [i,k, ... ,i] can only improve upon this if it has length less than zero, i.e. denotes a negative cycle;
• Thus, after the algorithm, (i,i) will be negative if there exists a negative-length path from i back to i.

1. 两种算法之间的某些区别:

1. Some differences between two algorithms:

• 矩阵算法可以找到具有特定边数的最小路径(例如，找到具有边数< = k的所有顶点对之间的最小路径)，FW无法.

• Matrix algo can find minimal path with specific number of edges (for example, to find minimal pathes between all pairs of vertices with number of edges <= k), FW cannot.

矩阵乘法算法需要O(n ^ 2)额外的空间，可以就地使用Floyd-Warshall.

Matrix multiplication algorithm requires O(n^2) additional space, Floyd-Warshall can be used in-place.

矩阵乘法算法具有O(n ^ 3 * log(n))复杂度，并且已重复或O(n ^ 4)的简单实现，Floyd-Warshall的复杂度为O(n ^ 3)

Matrix multiplication algorithm has O(n^3*log(n)) complexity with repeated squaring or O(n^4) with simple implementation, Floyd-Warshall complexity is O(n^3)

这篇关于Floyd-Warshall和矩阵乘法图算法有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！