4

The problem is simple on paper... but a bit harder when it comes to write the algorithm to solve it.

Let's use the following graph:

enter image description here

First part

This graph has an entry point A and two possible exits B and J. I'm looking for a way to find the minimum and maximum number of nodes needed to go from entry to an exit (the plan is more to find the numbers from ANY node to an exit, but let's go from start to end for now).

In the graph above, the min length is obviously 1 (A -> B). The max distance is trickier to find because of node E which is linked to a "previous" node C and can create an infinite loop. If we exclude E the max length is 6 (A -> C -> D -> F -> G -> I -> B).

However if we keep E what's the best strategy here to avoid infinite loops?

  • Tag links when visited to avoid crossing a link twice?
    • it won't be possible to move after C again when coming from E
  • Set a high number to infinite loop (something like: exit when you have crossed this section more than 1000 times)?
    • every graph containing a tiny loop will have a max length of 1000 which is not relevant

What is the way to go? How to find the min / max distance the most relevant way possible?

Second part

Ultimately the goal is to get the min / max distance from any node of the graph (starting from C, G, or E for instance).

Also some conditions can be set to define which node can be crossed / linked to a given node. For example when you're on E, according to certain values and variable states, only G may be available...

Thanks for your help.

  • 1
    For the shortest path, dijkstra. For the longest... how do you define it? Sure, we will avoid infinite loops. However, what is wrong with reaching a dead end? when that happens, it means that the path does not lead to the destination, hence... it is not part of the path. If that interpretation is not ok for you, please clarify. If you set an arbirtrary high number of times a node can be traversed, then your resulting longest past is one that does a much loops it can before going to the target. Is that ok? Is that ill-formed? We need good requirements, good requirements have good defintions. – Theraot Aug 7 '18 at 9:33
  • 1
    See en.wikipedia.org/wiki/Longest_path_problem, this is an NP-hard problem. – Doc Brown Aug 7 '18 at 10:32
1

For the shortest path, start at the well known Dijkstra's algorithm.


When you're on E, according to certain values and variable states, only G may be available...

A simple solution - which I want to encourage you to implement - is to implement dijkstra such that it calls a function to get the outgoing links from a given node. You can then do your checks there. When the conditions change, you would then invalidate the results of the search, and execute it again.

Note: It is even better if you can mark nodes as invalidated. That way the algorithm can cache the lists of links and only reevaluate for the invalidated nodes.

That a given link or node could be unavailable is not really a problem if the graph cannot change while it is being used. You simply compute it for the graph as you have it.

Since this is a concern, I suppose that there is something that will be traversing the graph and it could find that it changed from one moment to the other... when that happens, this something has advanced some distance on the graph, and it makes sense to compute the path from the current position to the target on the modified graph.


I am not sure how do you want to define longest path...

Perhaps, a good definition for longest path is: the shortest path that maximizes the number of visited nodes. Under that definition, walking an infinite loop is not beneficial.

We would searching for the shortest path... but we need a new metric to call "distance". My initial intuition is to use a metric that does not increase when we visit a new node.

If the distance does not increase nor decrease when visiting a new node, then the following paths are the same length:

A -> B
A -> C -> F -> G -> I -> B

However, we want the second path to be better (I mean, "shorter", I mean, to have a lower value in the metric, I mean, to be preferible).

A simple solution is to decrease the metric when visiting a new node.

Notes:

  • A negative metric can be problematic. For path finding, it is not safe to use Dijkstra with negatives. We can normalize it to only positive values by using a sigmoid function before comparing.
  • We also need to encode the rule that distance is different depending on whatever or not we have visited a node. You can solve this by similar means to what I described for having parts of the graph unavailable. Except, instead of passing the current node to evaluate the available links, you pass the current path.

With this metric we have:

A B - length: -1

A C D F G I B - length: -6

A C D E G I B - length: -6

A C D E B - length: -4

A C D E J - length: -4

A C D E C D F G I B - length: -5
        ¯ ¯
A C D E C D E G I B - length: -3
        ¯ ¯ ¯
A C D E C D E B - length: -1
        ¯ ¯ ¯
A C D E C D E J - length: -1
        ¯ ¯ ¯
A C D E C D E C D E F G I B - length: -1
        ¯ ¯ ¯ ¯ ¯ ¯

Then our "longest" path is one of the two longer paths that does not loop (A C D F G I B or A C D E G I B).

In case it is not evident, a path with a loop is always considered worse than its variant without loops because the loop traverses visited nodes, and thus increases the metric. And remeber that we are minizming the metric.

If you are using Dijkstra with a sigmoid of this metric - as I suggest - the loops will be discarded because - as explained above - they will always yield worst paths that those without loop.

Addendum: After posting the answer, I notice that I got some interesting results... for instance: A C D E C D F G I B manages to visit more nodes than A C D F G I B but scores worse (higher), that is not what I expected. I suppose we can tweak it to be more or less interested in going out of its way to reach more nodes before going to the target by applying factors to the added or decreased distance... for example, we could increase only half the value when traversing a visited node. What is the ideal proportion to increase? I have no idea. For practical purposes it can be tweaked to suit the design or problem domain.

1

A curious problem, as mentioned in comments it appears to be an instance of the Longest path problem, which is NP-hard. There is should be exponential-time solution with backtracking though. For that you need some kind of bookeeping (flag, hashset) of what edges/nodes are already probed by the path.
The solution could be described as

  1. If current node is a goal node, record path if it is the longest/shortest so far
  2. If there is an unvisited edge leading to an unvisited node traverse it
  3. If there is no such edge, backtrack until you find node that has such edge (resetting the traversed flag on unrolled path part)
  4. Exit when you backtracked to the entry node and there are no edges avaiable (=path is empty)
1

First part:

If you know the entry point and the list of exit points, and in absence of any suitable heuristic, a trivial approach is to use , Dijkstra's algorithm for every (entry, exit) pair and keep only the shortest.

For the longest path, use a negative distance instead of the distance in the algorithm.

If you have an heuristic (e.g there's some geography in the graph), prefer the A* algorithm because it will be more efficient.

Now this is trivial, but not the most efficient: as you have a single starting point, you'd recalculate the distance of the same subpaths several time. So it could be interesting to adapt Dijkstra's algorithm, in order to stop only when all the target nodes are reached, and working simultaneously with the shortest and longest distance.

Second part

It's unclear what you try to achieve: minimal/maximal between any two nodes ? Or only from the entry points ?

As a general hint for this broader part, I'd suggest to look at spanning tree algorithms, and see how to exploit the result for your purpose.

For example, if you construct a minimum spanning tree(MST), you will have an acyclic graph which contains all the shortest path between any connected nodes. So you would not need to run Dijkstra's algorithm for every possible pair; you'd just need to find the sole path in the MST that contains the two nodes. (Note: the term "tree" could be misleading: here it's not about a tree constructed and balanced around a root node, but a tree in the sense if the graph theory, that is an acyclic graph with only one path between any two nodes)

MST have several other application in graph optimisations.

Note that if your graph contains several independent connected components (group of nodes that are reachable between them), you'll need a forest of spanning trees (one tree per connected components). If you use for the spanning trees a data structure that easily provides the set of nodes in the tree, you'd be able to find very easily if 2 nodes are connected: they both must belong to the set of nodes of the same spanning tree.

  • @DocBrown I was thinking in particular of the minimum spanning tree, which by construction contains no cycle: en.m.wikipedia.org/wiki/Minimum_spanning_tree and are very suitable for network optimisation problems. – Christophe Aug 7 '18 at 13:48
  • @DocBrown because Dijkstra's algorithm builds a partial spanning tree to find the shortest path between two points, and the minimum spanning tree contains all the shortest paths between any connected nodes in the graph. So I think it is completely relevant here (and more efficient than executing Dijkstta between any combination of 2 nodes). But as said in my answer, the second part of the question is not precise enough, so I can't judge if this is really what OP is looking for. – Christophe Aug 7 '18 at 13:58
  • @DocBrown in the second part, if you want to know the shortest distance between any two node of the graph (e.g. G and E), you just have find the sole path that links the two nodes in the spanning tree. Maybe it's worth to underline that we don't see the spanning tree as a btree constructed and balanced around a root node, but just as a simple acyclic graph. And of course if there are several connected components in the general graph, you'll need a forest of minimum spanning trees (one tree per connected component) ;-) – Christophe Aug 7 '18 at 14:43
  • Ok, after rereading the question, I guess I misinterpreted it, deleted my comments. – Doc Brown Aug 7 '18 at 14:59
  • @DocBrown no problem! But your constructive comments showed that I was not clear enough. So I edited the second part, trying to clarify what I meant, so that readers don't have to go through all the comments :-) – Christophe Aug 7 '18 at 15:02
0

Check out Goal Orientated Action Planning

https://gamedevelopment.tutsplus.com/tutorials/goal-oriented-action-planning-for-a-smarter-ai--cms-20793

This allows you to set your conditions for available nodes.

However, the problem with loops is more difficult. You will have to define what you count as a repetition and its not as simple as visiting the same node twice.

for example you could consider the longest path in your example as

A C D E C D F G I B

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.