ダイクストラ最初のノードは、私が説明しましょう、私はC++でダイクストラプログラムを実施していると私はいくつかの問題を抱えている

Question

を訪問しましたコードは、ソースから他のすべての頂点までのフルパスを出力します。 私は配列int親を使用しています[num_vertexs];パスを保存します。しかし問題は、私が完全な経路を望んでいないことです。最初の頂点だけが訪れました。

最初のノードだけを訪問するにはどうすればよいですか？各ノードの親配列の最初のノードだけを印刷する方法はありますか？

ありがとうございます。

編集： 元の頂点から他のすべての頂点までの完全なパスを含む親配列を印刷する関数を表示します。

void printPath(int parent[], int j){ 
// Base Case : If j is source 
if (parent[j]==-1) 
    return; 

printPath(parent, parent[j]); 

printf("%d ", j); 

}

この関数は、完全なパスを出力しますが、私は唯一のパスの最初の頂点をしたいです。問題は、printf命令が完全なパスを出力するため、各頂点の最初のものだけをどのように印刷するのか分かりません。どうすればいいですか？ありがとうございました！

Answer 1

この関数は再帰的です。最後の頂点を除くすべてのパスを印刷するように呼び出され、最後の頂点が印刷されます。最初の頂点を印刷することを制限する簡単な、粗方法は、残りの部分を排除することである。

：

void printFirstStep(int parent[], int j){ 
    // Base Case : If j is source 
    if (parent[j]==-1) 
    return; 

    printFirstStep(parent, parent[j]); 

    if (parent[parent[j]]==-1) 
    printf("%d ", j); 
} 

より良い方法は、反復的に再帰からコード（すなわち、非再帰的である）を変更することです

void printFirstStep(int parent[], int j){ 
    // Base Case : If j is source 
    if (parent[j]==-1) 
    return; 

    while(parent[parent[j]] != -1) 
    j = parent[j]; 

    printf("%d ", j); 
} 

が（それはあなたが再帰を理解し、あなたの質問から明らかではありません。あなたに多くの良いを行うことはありませんあなたのコードにそれらを貼り付け、あなたがいない場合は、これらの機能を理解していることに注意してください。）