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.
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?
- You can determine the existence of negative cycles with 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.
Some differences between two algorithms:
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.
Matrix multiplication algorithm requires O(n^2) additional space, Floyd-Warshall can be used in-place.
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)
