0
$\begingroup$

I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes.

One method is :

let say we want path from $u$ to $v$, let $w$ be the vertex in which we are after exactly $k$ edges. If the walk is shortest, we must get from $u$ to $w$ using a shortest walk with exactly $k$ edges (compute $D^k$ using Min-plus matrix multiplication) and then from $w$ to $v$ using Floyd-Warshall algorithm to compute all pair shortest distance.

Other method is what I don't understand and needed help with:

Calculate all pair shortest distance matrix using Floyd-Warshall algorithm and then compute $D^k$ using Min-plus matrix multiplication from that matrix, and every entry of it corresponds to the least path of length atleast $k$.

Needed some hints regarding correctness of second method also is doing such thing is a well known algorithm/method?

Thanks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.