es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

PROLOG: el camino más largo en un grafo

24 May, 2023 Programación

Tengo este algoritmo para el camino más corto en un grafo, pero ahora necesito adaptarlo para obtener el camino más largo, es decir, el camino con un valor más alto en las aristas.

ruta(X,Y,[X,Y],L):-
arista(X,Y,L).

ruta(X,Y,[X|W],L):-
arista(X,Z,L1),
ruta(Z,Y,W,L2),
L is L1 + L2.

caminoMasCorto(X,X,[X,X],0):- !.
caminoMasCorto(X,Y,RutaMin,DistMin):-
findall([L,R],ruta(X,Y,R,L),Set),
sort(Set,Ordenado),
Ordenado = [[DistMin,RutaMin]|_].

¿Alguna ayuda?

Gracias.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para adaptar el algoritmo y obtener el camino más largo, se puede modificar el predicado shortestPath para usar el predicado max_member en lugar de sort y findall. El predicado max_member devolverá el elemento máximo de una lista. El predicado modificado quedaría así:

    longestPath(X,X,[X,X],0):- !.
longestPath(X,Y,MaxP,MaxD):-
    findall([L,P],path(X,Y,P,L),Set),
    max_member([MaxD,MaxP],Set).

Comments are closed.