重み付けされていないグラフの最短経路

Question

重み付けされていないグラフから最短経路を見つけて印刷する方法を見つけるには、特定の位置から開始し、次に2番目の整数が見つかるまで進みます。私はたくさんのことを試しましたが、何も私が探している結果を与えるものではありません。あなたの時間をありがとう、私は下のクラスを含めることになります。あなたが見てみる場合は

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

あなたが最短経路としてparentリストを印刷している、このリストは基本的に、あなたはおそらく欲しいものではありませんqueueから削除されたすべての要素のコピーです。

ノード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