How to find shortest path in prolog with weighted graph
I have this code :
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
This will follow a depth first search strategy, but the result is that it will give me all the paths, and it won't show which is the shortest. Is it possible to still use that strategy and find the shortest path? if not, what search strategy to use? and how can I implement it.
prolog depth-first-search shortest-path uniform-cost-search
edited Nov 13 '18 at 0:22
false
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
add a comment |
I have this code :
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
This will follow a depth first search strategy, but the result is that it will give me all the paths, and it won't show which is the shortest. Is it possible to still use that strategy and find the shortest path? if not, what search strategy to use? and how can I implement it.
prolog depth-first-search shortest-path uniform-cost-search
edited Nov 13 '18 at 0:22
false
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
add a comment |
I have this code :
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
This will follow a depth first search strategy, but the result is that it will give me all the paths, and it won't show which is the shortest. Is it possible to still use that strategy and find the shortest path? if not, what search strategy to use? and how can I implement it.
prolog depth-first-search shortest-path uniform-cost-search
edited Nov 13 '18 at 0:22
false
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
I have this code :
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
This will follow a depth first search strategy, but the result is that it will give me all the paths, and it won't show which is the shortest. Is it possible to still use that strategy and find the shortest path? if not, what search strategy to use? and how can I implement it.
prolog depth-first-search shortest-path uniform-cost-search
prolog depth-first-search shortest-path uniform-cost-search
edited Nov 13 '18 at 0:22
false
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
edited Nov 13 '18 at 0:22
false
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
edited Nov 13 '18 at 0:22
false
10.2k770143
edited Nov 13 '18 at 0:22
false
10.2k770143
edited Nov 13 '18 at 0:22
false
10.2k770143
10.2k770143
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
asked Nov 10 '18 at 19:08
John SallJohn Sall
816
816
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
I think there are problems with your code:
TDist=TD1+TD2doesn't compute the sum, use is/2 instead, at least when a path is returned.It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.
We can't say what the actual path will be, just its value.
Anyway, library(aggregate) can be used to find the shortest path. For instance
?- aggregate(min(D), path(a,g,D), D).
D = 8.
Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53242473%2fhow-to-find-shortest-path-in-prolog-with-weighted-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I think there are problems with your code:
TDist=TD1+TD2doesn't compute the sum, use is/2 instead, at least when a path is returned.It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.
We can't say what the actual path will be, just its value.
Anyway, library(aggregate) can be used to find the shortest path. For instance
?- aggregate(min(D), path(a,g,D), D).
D = 8.
Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
add a comment |
I think there are problems with your code:
TDist=TD1+TD2doesn't compute the sum, use is/2 instead, at least when a path is returned.It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.
We can't say what the actual path will be, just its value.
Anyway, library(aggregate) can be used to find the shortest path. For instance
?- aggregate(min(D), path(a,g,D), D).
D = 8.
Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
add a comment |
I think there are problems with your code:
TDist=TD1+TD2doesn't compute the sum, use is/2 instead, at least when a path is returned.It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.
We can't say what the actual path will be, just its value.
Anyway, library(aggregate) can be used to find the shortest path. For instance
?- aggregate(min(D), path(a,g,D), D).
D = 8.
Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
I think there are problems with your code:
TDist=TD1+TD2doesn't compute the sum, use is/2 instead, at least when a path is returned.It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.
We can't say what the actual path will be, just its value.
Anyway, library(aggregate) can be used to find the shortest path. For instance
?- aggregate(min(D), path(a,g,D), D).
D = 8.
Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
answered Nov 10 '18 at 19:35
CapelliCCapelliC
51.1k43262
51.1k43262
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
add a comment |
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
Do you think there's any other way to do this? by combining the goal code into the code itself? So only what I will put in the goal is path(a, g, D).
– John Sall
Nov 26 '18 at 18:48
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
sorry, could you elaborate ? I don't understand the question... of course, the changes required to get a more functional path/3 are described as problems. a) use is/2 b) check if a node already has been visited. Here you have some choices, the most basic is to add a Visited accumulator to path/3, that become path/4 and use +member(Node,Visited) as a filter before the recursive call. c) Visited can also be returned 'tagging' it by the distance, to know the actual path found. There are plenty of answer on SO, but Iet me know if you are still lost.
– CapelliC
Nov 26 '18 at 19:14
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53242473%2fhow-to-find-shortest-path-in-prolog-with-weighted-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
