증가하는 에지를 가진 그래프의 최단 경로

Question

나는 지향 그래프를 가지고 있으며 Q 쌍의 노드 (A, B) 사이에서 최단 경로를 찾아야합니다. 그러나 그 길은 최대로 올라 가야합니다. 이러한 가장자리의 N 모서리와 길이가 증가해야합니다 (A에서 B (1,3,5,9)까지). 출력은이 경로의 길이입니다. (존재하지 않으면, 출력 -1).

그림은 그래프의 예입니다. 1 L와 제 4 포토 경로 그래프

가 = 2 (3)로부터는 L로, = -1없는 = 2 L로 1 내지 12 을 갖는다 = 5는 길이 29

인 그래프를 3D arraylist로 표현하려고 시도한 다음 조건을 채우는 최단 경로를 재귀 적으로 찾았지만 무엇이 잘못되었는지를 모릅니다.

이

public static int path(int v, int c, int mv, int dc, int pv) { 
    if (pv==mv) { 
     if (Gi.get(v).contains(c)) { 
      return G.get(v).get(c).get(0); 
     } 
     return -1; 
    } 
    bol[v]=true; 
    for (int i=0; i<G.get(v).size(); i++) { 
     for (int j=0; j<G.get(v).get(i).size(); j++) { 
      if (!bol[Gi.get(v).get(i)]) { 
       if (G.get(v).get(i).get(j)>dc) { 
        int ce=path(Gi.get(v).get(j),c,G.get(v).get(i).get(j),dc,pv+1); 
        if (ce!=-1) return ce; 
       } 
      } 
      else { 
       return -1; 
      } 
     } 
    } 
    return vz; 
} 

누군가가 나를 도울 수 :
이 코드는 작동하지 않습니다, 무한 재귀입니까?

감사합니다, Ferko

당신은 최소 우선 순위 대기열 및 경로를 나타내는 단일 연결된 목록 데이터 구조와 함께 할 수

Answer 1

:

import java.util.LinkedList; 
import java.util.PriorityQueue; 

public class DijkstraTest 
{ 
    public static PathSegment Dijkstra(
     final Vertex from, 
     final Vertex to, 
     final int maxSize 
) 
    { 
    if (from == null) 
     throw new IllegalArgumentException("From vertex cannot be null"); 
    if (to == null) 
     throw new IllegalArgumentException("To vertex cannot be null"); 
    if (maxSize <= 0) 
     throw new IllegalArgumentException("Maximum size must be at least 1"); 
    final PriorityQueue<PathSegment> queue = new PriorityQueue<>(); 

    for (final Edge e : from.outEdges) 
     queue.add(new PathSegment(e, null)); 

    while (!queue.isEmpty()) 
    { 
     final PathSegment p = queue.poll(); 
     final Edge e = p.edge; 
     final Vertex v = e.to; 
     if (v == to) 
     { 
     // Found a path to destination 
     return p; 
     } 
     if (p.size == maxSize) 
     { 
     // Not reached the destination but at max length so discard this path 
     continue; 
     } 
     for (final Edge o : v.outEdges) 
     { 
     if (o.length > e.length) // Increasing edges 
     { 
      queue.add(new PathSegment(o, p)); 
     } 
     } 
    } 

    return null; 
    } 

    public static class Vertex{ 
    public final int index; 
    public final LinkedList<Edge> outEdges = new LinkedList<>(); 
    public Vertex(final int i) 
    { 
     index = i; 
    } 
    } 

    public static class Edge{ 
    public final Vertex from; 
    public final Vertex to; 
    public final int length; 
    public Edge(final Vertex f, final Vertex t, final int l) 
    { 
     from = f; 
     to = t; 
     length = l; 
     from.outEdges.add(this); 
    } 
    } 

    public static class PathSegment implements Comparable<PathSegment>{ 
    public final Edge edge; 
    public final PathSegment prev; 
    public final int length; 
    public final int size; 
    public PathSegment(final Edge e, final PathSegment p) 
    { 
     edge = e; 
     prev = p; 
     size = (prev == null ? 0 : prev.size) + 1; 
     length = (prev == null ? 0 : prev.length) + edge.length; 
    } 

    @Override 
    public int compareTo(final PathSegment p) 
    { 
     return Integer.compare(length, p.length); 
    } 

    @Override 
    public String toString(){ 
     return (prev == null ? Integer.toString(edge.from.index) : prev.toString()) 
      + ',' 
      + Integer.toString(edge.to.index); 
    } 
    } 

    public static void main(final String[] args) 
    { 
    final Vertex[] vertices = { 
     new Vertex(1), new Vertex(2), new Vertex(3), new Vertex(4), new Vertex(5), new Vertex(6) 
    }; 

    final Edge[] edges = { 
     new Edge(vertices[0],vertices[1],2), 
     new Edge(vertices[0],vertices[2],7), 
     new Edge(vertices[0],vertices[5],5), 
     new Edge(vertices[1],vertices[0],11), 
     new Edge(vertices[1],vertices[2],3), 
     new Edge(vertices[2],vertices[3],8), 
     new Edge(vertices[2],vertices[4],1), 
     new Edge(vertices[3],vertices[1],10), 
     new Edge(vertices[3],vertices[4],6), 
     new Edge(vertices[5],vertices[3],4), 
     new Edge(vertices[5],vertices[3],7) 
    }; 

    PathSegment p; 

    p = Dijkstra(vertices[0], vertices[3], 2); 
    System.out.println(p + " - length: " + (p==null?"null":p.length)); 

    p = Dijkstra(vertices[2], vertices[0], 2); 
    System.out.println(p + " - length: " + (p==null?"null":p.length)); 

    p = Dijkstra(vertices[2], vertices[0], 3); 
    System.out.println(p + " - length: " + (p==null?"null":p.length)); 
    } 
} 

이 출력 :

1,6,4 - length: 12 
null - length: null 
3,4,2,1 - length: 29