開始頂点、その他の頂点、エッジなどのグラフが与えられたとき、ある頂点から別の頂点に向かうコストを表します。最初の頂点から移動できる行き先の頂点のセットを見つける必要があります。予算は一定の金額であり、旅行の総費用は予算内でなければなりません。どのようにしてこの問題にDijkstraのアルゴリズムを実装できますか？私は通常、Dijkstraを使って2つの固定された頂点間の最短経路を見つけ出すと考えています。しかし、この予算問題でダイクストラを実装する方法がわかりません。誰かがアイディアを与えることができれば、本当に役立ちます！Dijkstra - 予算内の目的地を見つける
Dijkstraのアルゴリズムは、single-source shortest pathの問題を解決しました。これは、結果として生じるデータ構造が、開始ノードをルートとするツリーであることを意味する。典型的には、実装は、開始ノードから各ノードに到達するための最小コストを格納する。合計で、予算内で到達可能な頂点のセットは、最短パスのコストが予算を超えないものです。アルゴリズム自体は変更する必要はありません。追加のステップでは、バージン内で到達可能なノードを出力として返さなければならない。あなたは、ダイクストラのアルゴリズムを使用する場合
は、以下のシナリオで終わることができる：50の予算と4つのノード（開始ノード1、ノード2、ノード3）
スタートのグラフを仮定
ノード - >ノード1（15） - >ノード2（10）：そう総コストは25
開始ノードである - >ノード3（15）：総コストは15
だから今、あなたの予想結果は何であります？ノード1からノード2に移動し、ノード3を無視する必要があります（開始に戻ることはできず、ノード3に戻ることができます。戻り値も30になります）。または、ノード1に戻り、ノード3に行きます（合計費用45、利用可能な最大コスト）
Floyd-Warshallのすべての宛先をカバーする最短経路ではありませんアルゴリズムhttps://en.wikipedia.org/wiki/Floyd -Warshall_algorithm
1.開始点と他のすべての頂点間の最短経路を決定します。 2.各旅行の価格。 3.どの旅行が予算内にあるかを決定する。 – DwB