Finding the shortest distance between two nodes given multiple graphs

user_10207525 0
Viewed 295

Assume that we have a set of nodes and multiple graphs with different edges. I need to find the shortest path between two nodes. as an example given, there are three graphs as graph 01, graph 01 & graph 03 as shown in the figure. I need to find the shortest path between node 1 & node 7. enter image description here

since there is no path in one graph, I have used multiple graphs. therefore the result should be like shown below. enter image description here

though the below-shown path is used less number of edges compared above graph, since conversions between graphs are higher, the above path should be considered as the shortest path.

enter image description here

here, the most important term for a path to be shortest is the number of conversions from graph to graph. how can I solve this problem?

shortest-path graph-theory algorithm
2 Answers

The diagrams may be a bit misleading in this case. If the measure of distance for the purpose of "shortest path" is how many conversions between graphs happen on the route, then for each individual graph, we have edges of weight 0 between any pair of connected nodes (nodes that are reachable from each other within the same graph).

We then have edges of weight 1 between pairs of shared nodes between graphs.

user_20347870

Create a new graph in which:

  1. A node is defined as (graphID, u) which represents a node u that is only reachable by using as last edge ones that belongs to the graph 'graphID'.

  2. An edge between the nodes (graphID1, u1) and (graphID2, u2) has weight zero if 'graphID1' is equal to 'graphID2', and zero otherwise.

Finally, run a BFS 0/1 over your new graph considering multisources: (0, source), (1, source) and (2, source) and to get the answer you have to consider these possible targets in the new graph: (0, target), (1, target) and (2, target).

The complexity is O(V + E).

Check my code for further details: ideone.com/iDlm38

user_163214910
Related