I'm going over a lecture recording, in it my professor mentions using Dijkstra's algorithm (or a modified version of it) to find multiple-source to single source shortest paths, e.g. finding the closest hospital out of three hospitals to an accident site.

I have no visuals to see what he is doing on the blackboard, but he describes creating a new 'virtual node' that has a node degree equal to the number of sources, with each edge linking to each intended source, and the cost of this node's edges are 0. I guess the process is that the new virtual node becomes the source, and as each of its edges connect to a real sources for zero cost, it would be computing shortest paths from each source in the most efficient manner.

Is this correct?

  • please can u draw the diagram that can show the multiple source of the dijkstra algorithm – user36328 Aug 27 '14 at 15:07
  • @user36328, sometimes Wikipedia can be useful :) en.wikipedia.org/wiki/Dijkstra%27s_algorithm – Joseph Aug 27 '14 at 15:11

Yes, that should be OK. But adding such a virtual node can be costly in terms of CPU-time and in a multi-user environment it may also be undesirable. It may be faster to calculate from the accident site and then reverse the oneway restrictions while doing so. Stop once the first hospital has been reached.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.