# Shortest-Path for Weighted Directed Bipartite Graphs

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.

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

• 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?
– Raphael
Sep 21 '15 at 7:33

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.

• 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. Sep 21 '15 at 12:40
• @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?