7

I'm working with a weighted, undirected multigraph (loops not permitted; most node connections have multiplicity 1; a few node connections have multiplicity 2). I need to find the shortest path between two subgraphs of this graph that do not overlap with each other. There are no other restrictions on which nodes should be used as start/end points.

Edges can be selectively removed from the graph at certain times (as explained in my previous question) so it's possible that for two given subgraphs, there might not be any way to connect them.

I'm pretty sure I've heard of an algorithm for this before, but I can't remember what it's called, and my Google searches for strings like "shortest path between subgraphs" haven't helped. Can someone suggest a more efficient way to do this than comparing shortest paths between all nodes in one subgraph with all nodes in the other subgraph? Or at least tell me the name of the algorithm so I can look it up myself?

For example, if I have the graph below, the nodes circled in red might be one subgraph and the nodes circled in blue might be another. The edges would all have positive integer weights, although they're not shown in the image. I'd want to find whatever path has the shortest total cost as long as it starts at a red node and ends at a blue node. I believe this means the specific node positions and edge weights cannot be ignored.

enter image description here

(This is just an example graph I grabbed off Wikimedia and drew on, not my actual problem.)

Improve this question
4
  • 1
    add a imaginary node that connects to all nodes of one set and use that as your starting or end point
    – ratchet freak
    Aug 23, 2014 at 19:55
  • @ratchetfreak I'm not understanding how that would help, could you give a little more detail?
    – Pops
    Aug 23, 2014 at 20:10
  • It removes the complexity of the subgraphs as the first and last edge is a 0-cost from the imaginary start or to the imaginary end, then all you need to worry about is the disappearing edges
    – ratchet freak
    Aug 23, 2014 at 20:12
  • It's not reasonable to simplify a subgraph that way, though; there may be multiple edges leading out of a given subgraph, with various different weights, from multiple different nodes. Using a single imaginary node as the sole entry/exit point doesn't account for that.
    – Pops
    Aug 23, 2014 at 20:16

2 Answers 2

Reset to default
4

You should be able to adapt Dijkstra's algorithm.

Just add two points A & B to your graph, which are connected to one of the subgraphs each. Then calculate the shortest path between the two points A & B.

The shortest path between the two subgraphs should be the path that you get after removing A & B from the result.

Improve this answer
7
  • It seems like you have the same idea as ratchet freak did in his comment under my question, which makes me think maybe I did a poor job of writing the question. The distance from one node in subgraph A to an arbitrary node N outside of subgraph A may be very different than the distance from some other node in subgraph A to node N. Thus, it's not okay to simplify away the entire subgraph in the way you suggest (or, I'm misunderstanding your approach).
    – Pops
    Aug 23, 2014 at 20:53
  • @Pops but that would result in the cheaper path being traversed first
    – ratchet freak
    Aug 23, 2014 at 21:19
  • @ratchetfreak ohhh, I see what you (both) mean now. Temporarily replace each subgraph with a fake node, and reassign all edges that previously touched each subgraph to touch the corresponding fake node instead. Yeah, that'll do it. Hrm, gonna be a pain to actually implement, though.
    – Pops
    Aug 23, 2014 at 21:31
  • 2
    @Pops or my first idea: a 0-cost (or uniform cost) connection to all nodes in one subgraph from the fake node, much easier :)
    – ratchet freak
    Aug 23, 2014 at 22:00
  • Instad fake nodes or 0 cost connections, I would vote to just use Djikstra with the difference that the starting node is changed to a set of nodes (after all, the starting node is just an special case of the "set of nodes already visited") and the ending node is not one, but any one inside another set.
    – SJuan76
    Aug 23, 2014 at 22:08
1

After struggling for a day trying to shoehorn fake nodes and edges into my poorly designed code, I'm beginning to think that SJuan76's suggestion is really quite elegant. I can't prove that it works in all cases, but I've run through a few examples by hand and it seems to do okay.

Start with plain old Dijkstra's Algorithm. Make the following minor changes:

  • The regular algorithm sets all initial distances to infinity other than "the source node." Instead, set all initial distances to infinity. Then, change the distance to zero for each node in the "start" subgraph. (For an undirected graph like mine, you can just pick either subgraph.)

  • Keep running the algorithm normally until the only nodes that remain in the unvisited set are nodes in the "end" subgraph. It's safe to stop at this point because they can only possibly make distances larger, not smaller. (If you have negative edge weights, this doesn't apply.)

  • Look through all of the nodes in the "end" subgraph, and pick the one that has the lowest total score. That's the end node.

  • Follow the path of saved "previous node" info until a node in the "start" subgraph is reached.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.