Re: graph path searching

<timasmith@xxxxxxxxxxx> wrote in message
news:1132797570.728092.131130@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> So what I have done so far is removed the complexity of a weighted
> graph and tackled it by the following.
>
> So suppose I have n nodes where n>1 in an undirected unweighted graph.
>
> I get the shortest path between the first 2 nodes using bfs (code
> below) and add to a nodelist called listnode
>
> foreach node in remaining nodes
> foreach node2 in listnode
> dist = shortestpath(node,node2)
> if dist < mindist then mindist = dist
>
> So this seems to work - but I am not sure whether it meets the goal of
> minimum number of nodes in total?
>
>
>
> search(X,Y,Route) :- search(X,Y,[[X]],Route).
> search(X,X,[[X]],[X]).
> search(X,Y,[[Y|Path]|_],[Y|Path]).
> search(X,Y,[Path|Paths],Route) :-
> expand(Path,Alternatives),
> append(Paths,Alternatives,Paths1),
> search(X,Y,Paths1,Route).


"X" and "Y" are unused.
As far as I can tell, they are never instantiated,
never given values, except by accident.
So you can remove them from this code.

--
Martin Sondergaard,
London.


.

Relevant Pages

  • Re: Arrays as key in a HashMap
    ... Just because you have a contract about an interface, and it can be kept constant, does not mean that the code behind it needs to be as complicated as you can manage, or want to, create it. ... Can you solve that problem with less complexity, or do you just move the complexity elsewhere? ... The hash code is, of course, an optimization to avoid a linear search... ... But, using a hash code of the graph as a unique identifier of the graph is not the way to go, as you then have to take into consideration many factors that are quite complex, such as ...
    (comp.lang.java.programmer)
  • Re: Algorithmic complexity of a graph
    ... > Does by chance anyone know of a definition of the ALGORITHMIC (or ... > I have only found definitions of computational complexity... ... bits necessary to describe a graph in such a system - for instance you ... the number of spanning trees is often called the "complexity" ...
    (sci.math.research)
  • Re: Graph Theory: Cutting a Graph into Two in an Artificial Chemistry
    ... I start with a graph that has a single connected component (such that ... then I count that as a valid way that my original graph ... The set of all 'valid' splits from is the answer I want. ... It would probably be useful to know the size and complexity of the ...
    (sci.math)
  • Re: Input size interpretation of Traveling Salesman Problem etc, quite basic.
    ... > the number of cities. ... > it should change the Big-O complexity. ... > are there governing how you define the size of the input? ... complexities for graph algorithms are typically given ...
    (comp.theory)
  • Re: Algorithmic complexity of a graph
    ... > bits necessary to describe a graph in such a system - for instance you ... Obviously it's the Kolmogorov complexity of the adjacency matrix, ... which can be easily encoded as a bitstring. ...
    (sci.math.research)