Floyd-Warshall 和矩阵乘法图算法有什么区别？
What is the difference between Floyd-Warshall and matrix multiplication graph algorithms?
我必须解决以下问题：编写一个程序，给定一个具有成本和两个顶点的有向图，找到给定顶点之间的最低成本步行，或者如果在负成本循环中打印一条消息图形。该程序应使用矩阵乘法算法。
我按照定义实现了矩阵乘法算法：伪矩阵乘法，其中加法被最小化代替，乘法被加法代替。但是通过这样做，我最终得到了 Floyd-Warshall 算法。另外，我无法通过这种方式轻松确定负成本循环的存在。
我认为我的算法与真正的矩阵乘法图算法之间存在重大差异，但究竟是什么？
- 您可以使用 Floyd-Warshall 确定是否存在负循环：
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Behavior_with_negative_cycles
Nevertheless, if there are negative cycles, the Floyd–Warshall
algorithm can be used to detect them. The intuition is as follows:
- 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.
两种算法的一些区别：
矩阵算法可以找到特定边数的最小路径（例如，找到边数<= k的所有顶点对之间的最小路径），FW不能。
矩阵乘法算法需要额外的O(n^2)space，Floyd-Warshall可以就地使用
矩阵乘法算法具有 O(n^3*log(n)) 复杂度，repeated squaring 或 O(n^4) 具有简单实现，Floyd-Warshall 复杂度为 O( n^3)
我必须解决以下问题：编写一个程序，给定一个具有成本和两个顶点的有向图，找到给定顶点之间的最低成本步行，或者如果在负成本循环中打印一条消息图形。该程序应使用矩阵乘法算法。
我按照定义实现了矩阵乘法算法：伪矩阵乘法，其中加法被最小化代替，乘法被加法代替。但是通过这样做，我最终得到了 Floyd-Warshall 算法。另外，我无法通过这种方式轻松确定负成本循环的存在。
我认为我的算法与真正的矩阵乘法图算法之间存在重大差异，但究竟是什么？
- 您可以使用 Floyd-Warshall 确定是否存在负循环：
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Behavior_with_negative_cycles
Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them. The intuition is as follows:
- 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.
两种算法的一些区别：
矩阵算法可以找到特定边数的最小路径（例如，找到边数<= k的所有顶点对之间的最小路径），FW不能。
矩阵乘法算法需要额外的O(n^2)space，Floyd-Warshall可以就地使用
矩阵乘法算法具有 O(n^3*log(n)) 复杂度，repeated squaring 或 O(n^4) 具有简单实现，Floyd-Warshall 复杂度为 O( n^3)