-
-
Notifications
You must be signed in to change notification settings - Fork 366
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
pgr_ksp doesn't give all correct shortest path #1891
Comments
@luisfernandos1 Reproduction:
Indeed it returns only 4 paths, I deduce that 5 paths are expected on the solution. which can visually be seen on the following visual representation of the graph and of the paths found
|
Is there any knews about this problem ? |
@luisfernandos1 |
Checking again
working the results by hand on next comment |
Expected path results: 1 -> 4 |
Problem
To Reproduce
In order to reproduce the problem just create a graph like a square, where all point are connected, let's say
A,B,C,D
you want to find path from A to D
There are the paths it is returning
AD
ABD
ACD
ABCD
Expectation
Should bring all paths including ACBD, which is not happening, not that this route is different from ABCD
Sample Data
select id, idvertexfrom as source, idvertexto as target, distance::double precision as cost from fiber
"id","source","target","cost"
1,1,2,10.0
2,2,4,10.0
3,1,3,10.0
4,3,4,10.0
5,2,3,10.0
6,1,4,10.0
select * from pgr_KSP('select id, idvertexfrom as source, idvertexto as target, distance::double precision as cost from fiber',1, 4, 10, false, false);
"seq","path_id","path_seq","node","edge","cost","agg_cost"
1,1,1,1,6,10.0,0.0
2,1,2,4,-1,0.0,10.0
3,2,1,1,1,10.0,0.0
4,2,2,2,2,10.0,10.0
5,2,3,4,-1,0.0,20.0
6,3,1,1,3,10.0,0.0
7,3,2,3,4,10.0,10.0
8,3,3,4,-1,0.0,20.0
9,4,1,1,1,10.0,0.0
10,4,2,2,5,10.0,10.0
11,4,3,3,4,10.0,20.0
12,4,4,4,-1,0.0,30.0
ONLY 4 path are returned !!!
Platform/versions
The text was updated successfully, but these errors were encountered: