我必须解决以下问题：写一个程序，给定一个有向图与成本和两个顶点，找到对应的顶点之间的最小代价散步，或如果在图中的负成本回路输出一条消息。 该计划将使用矩阵乘法算法。
我实现矩阵乘法算法，因为它被定义：伪矩阵乘法，其中添加是通过最小化和乘法并加入代替。 但是，这样做，我结束了与弗洛伊德 - Warshall算法同样，我不能轻易确定负成本周期的这种方式存在。
我假设有我的算法之间真正的矩阵乘法图形算法有很大的差异，但什么是什么呢？
Answer 1:
- 您可以确定与弗洛伊德 - 沃肖尔负周期的存在：
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Behavior_with_negative_cycles
尽管如此，如果有负周期时，Floyd-Warshall算法可以用于检测它们。 直觉如下：
- 的Floyd-Warshall算法迭代地修改顶点的所有对（I，J），包括其中i = j的之间的路径长度;
- 最初，路径（I，i）的长度是零;
- 路径[I，K，...，I]只能在这个改进，如果它具有的长度小于零，即表示负周期;
- 因此，该算法之后，（I，i）的将如果存在从i存在负长度路径返回至i是负的。
两种算法之间的一些差异：
矩阵算法中可以找到与边缘的特定数量的最小路径（例如，以找到所有顶点对之间的最小pathes与边数<= k）时，FW不能。
矩阵乘法算法需要为O（n ^ 2）额外的空间，弗洛伊德-沃肖尔可以就地使用。
矩阵乘法算法具有O（N ^ 3 *的log（n）），与复杂重复平方与简单的实现或为O（n ^ 4），弗洛伊德-沃肖尔复杂度为O（N ^ 3）
文章来源: What is the difference between Floyd-Warshall and matrix multiplication graph algorithms?
