Shortest path special alternatives

[pawel_s_golec]

Hi All

I have question regarding finding paths between points. I have graph as in picture and try to find shortest way from node A to node S.
That's simple(marked red), but I want to find alternatives which contains as less as possible nodes from shortest path.
I need "cypher" query which gives me e.g. following paths(relations between nodes are bidirectional)

A - B - D - E - F - K - R - S
A - C - J - L - P - R - S
A - C - I - N - O - P - R - S

In general, the more different the route from the shortest that is better with minimal number of nodes

[Joel]

I see your example paths, but "algorithmically" what do you want exactly? If you can describe that I'm confident it could be implemented. I'm going to guess it is a simplistic shortest path with no weighting, is that correct?

My first thought is to simply use a score of 1 for every relationship and then run the same query (unweighted). That would give shortest route by rel/node length, the resulting path list could still include the weight path of course, but would give a list of shortest paths with minimal nodes.

e.g. allShortestPaths()

If initialized with an non-existing weight-property, it will treat the graph as unweighted.

[pawel_s_golec]

Hi Joel
Thanks for your interesting. The thing what I want to achieve is find path from A to S which fulfil following conditions:

1. Path isn’t shortest.
2. Path which I want to find should be as much as possible different(contains other nodes) than shortest path, so e.g path A – C – j - H – M – R – S should be omitted because have three common nodes(H, M, R) besides of A and S
3. Path should have as less nodes as possible so for example path A – C – I – N – O – P – L – J – H – G – K – R – S also should be ommited
   Acceptable in this case are paths:
   A - B - D - E - F - K - R - S
   A - C - J - L - P - R - S
   A - C - I - N - O - P - R – S

You can imagine those paths as a railways where shortest path is crowded so train driver want to "escape" from this path and drive through another path as long as possible. That paths are longer than shortest one but often can be quickest so can be take in account as an alternatives

[Joel]

I think the railway analogy may be very helpful in understanding how to solve this.

You said, "shortest path is crowded so train driver want to escape", this means that the transit time for that path (relationship) is now high, so the shortest path (by transit time) is in fact by another route. As needed (e.g. crowded route occurs) update the cost/weights on the relationships (a track between stations) and then new routes will be returned by shortest path...

This is very similar to the example given in the manual here

[Joel]

one additional thought, it is possible to have multiple weight properties on each relationship, for example for transit there are multiple properties for each leg of a journey, .distance, .duration, .cost or something novel like .scenic_view (1/distance), that could be used to determine a desirable "shortest path" based on a preference.