# 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? Commented Sep 21, 2015 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.

A small illustration I made:

• 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? Commented Sep 20, 2015 at 14:45
• 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. Commented Sep 21, 2015 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
Commented Sep 21, 2015 at 15:14
• @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. Commented Sep 21, 2015 at 15:42
• @KlausDraeger Ah, right. If those edges are not equally expensive I suspect you can not significantly improve over Dijkstra.
– orlp
Commented Sep 21, 2015 at 15:52