3 replies to this topic

[Squeezy]

Good day, everyone!
Looks like I really need your help with my work on data structures. The task goes as follows:

For a given unweighted oriented graph G and two its vertices v' and v'', compute
- the shortest path between v' and v''
- (two tasks) all the possible paths between v' and v'' so that paths from any pair do not cross
a) with edges,
b) with vertices.

The first problem is obviously solvable by Breadth-First Search algorithm but I cant seem to puzzle out the second one.
Seemingly it's a recursion involving dynamic programming methods; ideally the solution should expand BFS. Perhaps there are already existing algorithms for that?..

Thanks in advance for any help!

[WingedPanther]

I would start by finding all paths that satisfy that property with respect to themselves:
IE find all paths such that the do not self-cross on vertices/edges.
Once that is done, you should have a reasonable space to search from.

[$AP]

Quote

all the possible paths between v' and v'' so that paths from any pair do not cross
a) with edges,
b) with vertices.

What does this actually mean? Is it the fact that in the path no vertices/edges occur twice? Then it can easily be done, as you mentioned, exploring BFS and using DP.

[WingedPanther]

He's talking about two different problems, one is the set of edge distinct paths, the other is the set of vertex distinct paths (excluding v' and v'')