I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination vertex. Also, all vertices in the source set are connected to all vertices in the bridge set, and all the vertices in destination set are connected to all the vertices in the bridge set.
Let $n$ be the cardinality of both the source and the destination set, and $m$ be the cardinality of the bridge set.
A naive algorithm can compute these in $\mathcal{O}(n^{2}m)$ comparisons. On the other hand, since we are computing $n^{2}$ quantities, so the complexity will be at least $\mathcal{O}(n^{2})$.
My guess is that it can be done in $\mathcal{O}(n^{2}\log m)$ using priority-queue. So question is, whether my guess is correct and if not, then what is the complexity of solving this problem?
Edit:
Note that shortest path between a vertex in the source set to any vertex in the bridge set is the direct link, and same holds for the shortest path between the bridge and destination set.