# 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

• 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. – Klaus Draeger 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? – orlp Sep 21 '15 at 15:14