가중치가 적용된 그래프의 최단 경로

Question

특정 위치에서 시작한 다음 두 번째 정수가 나타날 때까지 앞으로 이동하여 무게가없는 그래프에서 최단 경로를 찾아서 인쇄하는 방법을 찾으려고합니다. 나는 많은 것을 시도했지만 아무 것도 나에게 결과를 알려주지 않는다. 찾고 있던 모든 정수가 시작부터 끝까지 모든 정수를 제공한다. 시간 내 주셔서 감사 드리며 아래에 수업을 포함 할 것입니다.

public class graph { 
     int Vertices; 
     LinkedList<Integer> adjListArray[]; 
     Hashtable hs; 
     Hashtable hs2; 

     graph(int vertices) 
     { 
      this.Vertices = vertices; 
      adjListArray = new LinkedList[vertices]; 
      for(int i = 0; i < vertices ; i++){ 
       adjListArray[i] = new LinkedList<>(); 
      } 
     } 
    public void getHastables(Hashtable hs, Hashtable hs2) { 
     this.hs = hs; 
     this.hs2 = hs2; 
    } 

    public void addEdge(int v1, int v2) 
    { 
     adjListArray[v1].addFirst(v2); 


     adjListArray[v2].addFirst(v1); 
    } 

    public void printGraph() 
    {  
     for(int v = 0; v < Vertices; v++) 
     { 
      System.out.println("Adjacency list of vertex "+ v); 
      System.out.print("self"); 
      for(Integer pCrawl: adjListArray[v]){ 
       System.out.print(" -> "+pCrawl); 
      } 
      System.out.println("\n"); 
     } 
    } 
    ///////=================================================================================////////// 
///////=================================================================================////////// 
///////=================================================================================////////// 


    public void BFS(int start, int finish) 
    { 
     Map<Integer, Integer> prev = new HashMap<Integer, Integer>(); 
     int s = start; 

     boolean visited[] = new boolean[Vertices]; 
     LinkedList<Integer> queue = new LinkedList<Integer>(); 
     LinkedList<Integer> parent = new LinkedList<Integer>(); 
     visited[start]=true; 
     queue.add(start); 
     while (queue.size() != 0) 
     { 

       start = queue.poll(); 


       if(start == finish) { 

        break; 
      } 
      else { 

      Iterator<Integer> i = adjListArray[start].listIterator(); 
      while (i.hasNext()) 
      { 
       int n = i.next(); 
       if (!visited[n]) 
       { 
        visited[n] = true; 
        queue.add(n); 

        prev.put(n,start); 
       } 
      } 
      parent.add(start); 
      } 

     } 

    if(start != finish) { 
    System.out.println("there is no path between" + hs2.get(s) + " and " + hs2.get(finish)); 
    } 
    else { 
    System.out.println("Path between " + hs2.get(s) + " and "+ hs2.get(finish)); 
    System.out.print(hs2.get(s) + "-->"); 


    while(parent.size() != 0) { 
     System.out.println(hs2.get(parent.poll())); 
    } 

    ////////////////////////////////////////////// 

    int pos = finish; 
    while(prev.get(pos)!=null) { 
     System.out.println("try2 for prev " + hs2.get(pos)); 
     pos --; 
    } 

Answer 1

당신은 당신이 살펴 경우,이 목록은 사본 당신은 아마 원하는 것이 아니다 이는 queue에서 제거 된 모든 요소 기본적으로, 가장 짧은 경로로 parent 목록을 인쇄 할 수 있습니다.

노드 a에서 노드 b으로 도착했음을 알려주는 prev 맵이있는 경우이 정보를 역방향으로 사용하여 최단 경로를 재구성 할 수 있어야합니다. prev에 존재하지 않는 값을 찾을 때까지 대상에서 prev 맵을 탐색하면됩니다.

그냥 당신에게 아이디어를주고, 가능한 및 테스트하지 구현 될 수있다 :

int current = finish; 
Stack<Integer> stack = new Stack<>(); 
stack.push(current); // finish should go in the path 
while (prev.containsKey(current)) { 
    current = prev.get(current); 
    stack.push(current) 
} 
// now stack contains the shortest path