javaalgorithmdijkstra

how to find shortest path between multiple clusters


Dijkstra theorem talks about finding shortest path between two vertices.. But what if we have a matrix/graph which has clusters.. and now we need to find shortest path between these clusters ! distance between these clusters is in same way like it happens with between nodes having different weights.

As Matt recommended we can assume distance between nodes of cluster as zero.. which makes so much sense.. But, what if we want to find single shortest path so that ALL clusters are connected to each other..


Solution

  • Dijkstra's algorithm works basically the same way between two clusters as it does between two vertices. Start with all the vertices in the source cluster at distance 0, and proceed building incrementally longer paths until you find one of the vertices in the target cluster.

    If it helps, you can think of it this way: Connect all the vertices in both clusters together with 0-cost edges, and then find the shortest path from any specific source vertex to any specific target vertex. It won't matter which ones you choose, because the 0-cost edges ensure the everything in a cluster is at the same distance from everything else.