1
$\begingroup$

I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each edge has a non-negative weight of time. I look to find the shortest path between source and sink, given the weights and directions of the edges. The structure of the graph is quite simple, all adjacent zones are connected. The bipartite graph looks this this. enter image description here

My question is what is the best shortest-path algorithm for such a graph?

$\endgroup$
  • 3
    $\begingroup$ 1) Why are usual SSSP algorithms not good enough? 2) From the problem description alone, I'm not sure a bipartite graph is an accurate model. "because only adjacent zones can be connected" is not a sufficient argument; why can not three zones be pairwise adjacent? $\endgroup$ – Raphael Sep 21 '15 at 7:33
1
$\begingroup$

Merge every zone into one vertex. You now have a linear path, with one or multiple edges between each vertex. Since this graph does not branch, you can simply choose the cheapest edge between every vertex directly.

A small illustration I made:

graph

$\endgroup$
  • $\begingroup$ thank you so much, so essentially you are creating n edges between vertex 1 and 2, and the finding the edge which the lowest cost? Sorry for asking this dumb question but is there a name for this type of technique or algorithm? $\endgroup$ – user40019 Sep 20 '15 at 14:45
  • 2
    $\begingroup$ Looking at the picture in the question, this seems to add spurious solutions. Not every edge into zone $i$ can be followed by every edge out of zone $i$ due to the fact that there are several nodes in it. $\endgroup$ – Klaus Draeger Sep 21 '15 at 12:40
  • $\begingroup$ @KlausDraeger Well, if you look at the picture the asker posted, it seems that every node in zone $i$ is connected to every node in zone $i+1$. Could you give a counterexample from the picture of the asker? $\endgroup$ – orlp Sep 21 '15 at 15:14
  • 2
    $\begingroup$ @orlp True, but the title talks about weighted graphs, so I assumed that those edges are not all equally expensive. If they are, then of course your suggestion works nicely. $\endgroup$ – Klaus Draeger Sep 21 '15 at 15:42
  • $\begingroup$ @KlausDraeger Ah, right. If those edges are not equally expensive I suspect you can not significantly improve over Dijkstra. $\endgroup$ – orlp Sep 21 '15 at 15:52

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.