search all paths and the shortest path for a graph

2019-07-24 23:32发布

I have a problem in my code with turbo prolog which searches all paths and the shortest path in a graph between 2 nodes. The problem that i have is to test if the node is in the list or not (exactly in the clause of member)

           1    ---- b ----   3
           ---       |        ---
        ---          |             -----
      a              |5                  d
        ---          |             -----
            ---      |         ---
             2  ---  |     ---   4
                  -- c  --

for example we have for b--->c 
([b,c],5) , ([b,a,c],3) and ([b,d,c],7) : possible paths.
([b,a,c],3) : the shortest path.

and this is my code :

DOMAINS
    list=Symbol *

PREDICATES
    distance(Symbol, Symbol)
    path1(Symbol, Symbol, list, integer)
    path(Symbol, Symbol,list, list, integer)
    distance(Symbol, list, integer)
    member(Symbol, list)
    shortest(Symbol, Symbol, list, integer)

CLAUSES
    distance(a, b, 1).
    distance(a, c, 2).
    distance(b, d, 3).
    distance(c, d, 4).
    distance(b, c, 5).
    distance(b, a, 1).
    distance(c, a, 2).
    distance(d, b, 3).
    distance(d, c, 4).
    distance(c, b, 5).

    member(X, [X|T]).
    member(X, [Y|T]) :- member(X, T).

    absent(X, L) :-
        member(X, L),
        !,
        fail.
    absent(_, _).

    /* find all paths */
    path1(X, Y, L, C) :- path(X, Y, L, I, C).
    path(X, X, [X], I, C) :- absent(X, I).
    path(X, Y, [X|R], I, C) :-
        distance(X, Z, A),
        absent(Z, I),
        path(Z, Y, R, [X|I], C1),
        C = C1 + A
        .

    /* to find the shortest path */
    shortest(X, Y, L, C) :-
        path(X, Y, L, C),
        path(X, Y, L1, C1),
        C < C1.

2条回答
老娘就宠你
2楼-- · 2019-07-25 00:00

This shows the shortest path and it's weight:

edge(a,b,6).
edge(a,c,1).
edge(b,d,5).
edge(c,e,4).
edge(c,f,1).
edge(d,h,3).
edge(e,h,7).
edge(f,g,2).
edge(g,h,1).

path(X,Y,M,[Y]) :- edge(X,Y,M).
path(X,Y,P,[Z|T]) :- edge(X,Z,M),path(Z,Y,N,T),
            P is M+N.

pravilo(X,Y,Z) :-  assert(min(100)),assert(minpath([])),!,
                path(X,Y,K,PATH1),
                (min(Z),K<Z,
                retract(min(Z));assert(min(K))),
                minpath(Q),retract(minpath(Q)),
                assert(minpath([X|PATH1])),
                fail.

?- pravilo(a,h,X);
    write("Minimal Path:"),
    minpath(PATH),
    write(PATH),
    nl,
    write("Path weight:"),
    min(Z),
    write(Z).
查看更多
The star\"
3楼-- · 2019-07-25 00:13

Without knowing what the actual problem is, I can at least suggest that maybe shortest() and path() should take a maximum-length parameter that short-circuits the search.

Also, shortest() doesn't find the shortest path. It finds, for every possible pair of paths, the shortest of each pair.

查看更多
登录 后发表回答