Re: graph path searching

<timasmith@xxxxxxxxxxx> wrote in message
news:1132230148.596894.78020@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> Hi,
>
> I have seem some very simple algorithms to search for the shortest path
> between two nodes on an unweighted graph.
>
> What I would like to do is, given vertices 1..n, and given selected
> vertices k..m determine the shortest path of this weighted graph
> between the selected verticies.
>


When you say you need to find the shortest path,
does that mean that you know the distance between
any two of the verticies?
Or do you know a way of calculating it from other data?

> I also want the least number of vertices, but that would probably
> conflict with the shortest path so I'll ignore that for now.

You need to write one Prolog rule to find the shortest path,
and a different Prolog rule to find the least number of vertices.

Finding the smallest number of vertices is slightly easier,
so you might like to try to do that one first.

You could start by deciding how you want to represent the data
that you have, which you need for finding the result.
You would need to have this data in the form of Prolog facts.

Write some Prolog facts, then send them to this newsgroup,
and we may be able to think about the next step.


--
Martin Sondergaard,
London.


.

Relevant Pages

  • graph path searching
    ... I have seem some very simple algorithms to search for the shortest path ... between two nodes on an unweighted graph. ... between the selected verticies. ...
    (comp.lang.prolog)
  • Re: finding ALL shortest paths from i to j (not All pair shortest paths)
    ... > I have an undirected and unweighted graph. ... > I can easily compute the shortest path between a node i and j. ... (e.g., with breadth first search). ... So it suffices to enumerate all paths from i to j in the ...
    (comp.theory)