# Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem

At page 7 from these slides there is a Greedy algorithm I want to implement.

It says

let $$P_i$$ be the shortest path (if one exists) that [...]
connects some ($$s_j$$, $$t_j$$) pair that is not yet connected.

$$(s_j,t_j)$$ comes from a set of commodities.

Without getting into the theoretical implication of the whole algorithm, I only wonder how to implement such a statement.

It is stated to be greedy, hence it should have an easy implementation.

Is there a standard way to do that?

EDIT: Is there also any better reference than slides?

• Slides seem intentionally vague. Check out for example Fleischer (2000) page 8. The weights of the graph are updated according only when they are used. It's a bit like approximate column generation. Oct 20, 2022 at 18:10

## 1 Answer

Only the outer algorithm is greedy, in the sense of removing the path links in each iteration and never looking back. Use any algorithm (like Dijkstra) to find a shortest path for each remaining $$(s_j,t_j)$$ in each iteration. As a possible speed-up, you can skip Dijkstra for all $$j$$ for which none of its shortest-path links have been removed because in that case the previously computed shortest path will still be shortest.

• What about finding $P_i$. So far, I can only think of calculating all the possible shortest paths. Oct 20, 2022 at 8:06
• $P_i$ is not the shortest path between $(s_j,t_j)$. Rather $(s_j,t_j)$ is the couple connected by the shortest path $P_i$ in the graph. I can't figure out a better way to find this couple without computing all the paths per iteration. Oct 20, 2022 at 10:48
• I see. You are asking about a way to compute the minimum over $j$ of all shortest $s_j-t_j$ paths without explicitly recomputing them all. I amended my answer. Oct 20, 2022 at 12:42
• Thank you! Do you happen to know a better reference than the slides I shared?? Oct 20, 2022 at 13:10