2
$\begingroup$

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the shortest paths to transport the commodities between their respective source-sink pairs.

Is there any algorithm that can solve this kind of problem rapidly, possibly using topological sorting first? How is this affected if there is unlimited/limited capacity on the arcs?

Many thanks!

$\endgroup$
  • $\begingroup$ Sounds like the all-pairs shortest path problem, which can be solved with Floyd-Warshall $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 11 '13 at 15:44
  • $\begingroup$ Do any capacity restrictions or any other interactions between the commodities exist? If not what you can e.g. use Dijkstra on each pair independently. $\endgroup$ – frafl Jun 11 '13 at 19:31

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.