2

I have an undirected graph with about 1000 nodes and 2000 edges, a start node and an end node. I have to traverse from the start node to the end node passing through all the compulsory edges(which are about 10) while its not necessary to traverse through all the vertices or nodes. Is there an easy solution to this like some minor changes in the existing graph traversing algorithms? How do I do it?

Thanks for help.:)

This question is different from Find the shortest path in a graph which visits certain nodes as my question is regarding compulsory edges not vertices.

EDIT: The compulsory edges can be traversed in any order.

Community
  • 1
  • 1
Kashyap Kotak
  • 1,888
  • 2
  • 19
  • 38

1 Answers1

2

To start with a related problem, say you have a graph G = (V, E), 10 specific edges you must traverse in a given order E' = 1, ..., e10 > ∈ E, and a start and end nodes s, v ∈ V. You need to find the shortest distance from s to v using E' in the given order.

You could do this by making 10 copies of the graph. Start with a single copy (i.e., isomorphic t G = (V, E)), except that e1 moves from the first copy to the second copy. In the second copy (again isomorphic t G = (V, E)), remove e1, and have e2 move from the second copy to the third copy. Etc. In the resulting graph, run any algorithm to get from s in the first copy to e in the 10th copy.

Explanation: imagine intuitively that your graph G is drawn on a 2d sheet of paper. photocopy it so that you have 10 copies, and stack them up to a pile of 10 papers (imagine them with a bit of space between each two, though). Now change the graphs a bit so that the only way to go up to the second sheet, from the first sheet, is through an edge e1 leading from the bottom sheet to the second sheet. The only way to go up to the third sheet, from the second sheet, is through an edge e2 leading from the second sheet to the third sheet, and so on. You problem is to find the shortest path starting at the node corresponding to s on the bottom sheet, and ending at the node corresponding to e on the top sheet.

To solve the original problem, just repeat this with all possible permutations of E'. Note that there are 10! ~ 3.5e6 possibilities, which isn't all that much.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • I can traverse the compulsory edges in any order.... Sorry forgot to mention that – Kashyap Kotak Aug 07 '16 at 11:11
  • @KashyapC.Kotak That was clear from the question. My answer addresses that - see the last paragraph. – Ami Tavory Aug 07 '16 at 11:12
  • I am really not getting "moving from a copy to another". Sorry, but can you please elaborate a bit? – Kashyap Kotak Aug 07 '16 at 11:17
  • @KashyapC.Kotak See if the explanation helps you out. – Ami Tavory Aug 07 '16 at 11:22
  • 2
    To speed this up, I'd suggest first precomputing all pairs of shortest paths between the (up to) 20 vertices involved in the 10 compulsory edges (e.g. with the Floyd-Warshall algorithm, or repeated Dijkstra). After this, each of the 3.5 million permutations can be tested *much* faster. Note that you don't need to worry about the edge case that occurs when a compulsory edge ab happens to be on a shortest path between two others cd and ef, since you will at some point consider the permutation where ab appears between cd and ef, and *that* shortest path will be shorter. – j_random_hacker Aug 07 '16 at 16:53
  • 1
    Alternatively, you could build 2^10 = 1024 copies of the input graph, with one copy per possible subset of visited compulsory edges. (Transitions between copies happen similarly.) This should be much faster, since the time cost of a single shortest path gets multiplied by only 1024 instead of 3.5 million, but you may run out of memory! – j_random_hacker Aug 07 '16 at 16:57