0

2 点間の最短距離を見つけるコードを書いています。私のコードは今まで完璧に機能しています。つまり、通過する距離とパスを見つけるということです。この情報を印刷する必要がありますが、印刷機能を作成する必要があります。それが機能する方法は次のようなものです: たとえば、初期ポイントは 4 で、最終ポイントは 13 です。

それらの中間点をチェックするアルゴリズムを考え出す必要があります。4と13の間にポイントがあるとしましょう：7

4--7--13 次のように、それらの間のすべてのポイントをチェックする必要があります。

4--6--7--9--13 より具体的には、4-6 と 6-7 および 7-9 と 9-13 の間にポイントがあるかどうかをチェックします。したがって、次の反復では、次のような別のリストが形成される場合があります。

4--2--6--7--5--9--17--13 ここで、それらの間に中間値が存在しないとしましょう。そして、それが私が印刷すべきものです。あなたが私に与えるかもしれない助け、提案を本当に感謝します

4

2 に答える 2

2

Warshall-Floyd アルゴリズム (OP で使用) には、グラフのノード間の距離に加えてパスを決定できるバージョンがあります。

パス再構築によるフロイド・ウォーシャル アルゴリズム

ただし、これは最短経路問題を解決するための最良のアルゴリズムではないことに注意する必要があります。

于 2012-06-11T18:32:23.880 に答える
1

これは、再帰がこれを行うための最良の方法であるように思えます。すでに最短経路を見つけることができる場合は、2 点間の最短経路を見つけるために作成された関数があると仮定します。おそらく、リストを再帰的に分解し、最短パスを見つけて、そのポイントをリストに追加できます。

編集、申し訳ありませんが、質問を読み違えました。中間点を見つける必要があります。再帰関数にポイントのリスト全体を渡し、中間点を見つけます。存在する場合は、リストに追加します。中間点がない場合は、何も追加しないでください。リスト内の 1 つまたは 2 つのポイントである基本ケースに到達するまで、この関数を呼び出し続けます。

于 2012-06-11T18:09:10.543 に答える