問題タブ [shortest-path]

最短経路問題に最大コスト値を割り当てるにはどうすればよいのでしょうか。私の問題では、ノードに関連するリスクがあります。リスクを最小限に抑えたいのですが、ノード数が限られているソリューションを見つけてほしいと思います（たとえば、ソリューションがn個のノードを超えないようにしながら、ノードAからノードBへの最小リスクを見つけます）ありがとうございます多くの。

Johnson Algorithmの有用性を理解するのに苦労しています。この分野の知識を持っている人にとっては、この質問は本当にばかげているように聞こえるに違いないと思いますが、私には理解できません。ウィキペディアによると、ジョンソン アルゴリズムはベルマン フォード アルゴリズムを使用してエッジの重みを非負の重みに変換し、ダイクストラ アルゴリズムを使用して最短経路を見つけます。しかし、ベルマンフォードアルゴリズムも最短経路を見つけるアルゴリズムです。Bellman Ford Algorithm から取得した最短経路を使用しないのはなぜですか?

私はダイクストラのアルゴリズムを理解し、実装するために一日中戦ってきましたが、重要な結果はありませんでした。私は都市とその距離のマトリックスを持っています。私がやりたいのは、出発地と目的地を指定して、都市間の最短経路を見つけることです。

例：

これを解決する他の方法があるかどうか疑問に思い始めました。プリムのアルゴリズムを起点から適用し、作成されたツリー全体をループして、終点が見つかるとどうなりますか？

最短経路プログラムを書きたいです。アルゴリズムの仕組みは知っているが、どこから始めればよいか分からない

最初は、隣接行列を使用することを考えていましたが、スペースの関係で断念しました。今、隣接リストの方が良いと思います。

プログラムに入力を与えるために隣接リストの作成を開始する方法をウェブサイトまたはチュートリアルで教えてもらえますか?

タイトルが少し乱雑であることは知っていますが、それをよりよく説明する方法がわかりません。

私がやろうとしていること：

テキストファイルで見つかったグラフを使用して、頂点Aから頂点Bまでの最短経路（頂点の最小量）を見つけて印刷します。

注：ダイクストラ法ではなく、幅優先探索を使用します。

私が持っているもの：

グラフにBFSを適用する実用的なアルゴリズムですが、実際に最短経路を印刷する良い方法はありません。

最短経路の頂点と、アルゴリズムを介して実行されるが最短経路ではない頂点を区別するのに苦労しています。

例：0と4の間の最短パスを見つけます。0は1,2と3に接続します。1は4に接続します。私のパスは[0,1、1ではなく[0,1,2,3,4]になります。 4]。

同じ質問をしているスレッドや、これを含むBFSのウォークスルーを見つけることができなかったので、これを実際よりもはるかに難しくしているのかどうかわかりません。

編集：興味があるかもしれない人のためのコード（私がサークルを避けているかどうかはまったくわかりませんか？）

編集2：スタックへのパスを保存する方法を変更しました。

変数とメソッドの説明：

v=原点

w=ターゲット頂点

g=グラフ

vi=vの近傍を反復処理する通常の反復子

読んでくれてありがとう！

私は２軒の家を借りる必要があります。できるだけ近づけてほしい。約300戸の賃貸住宅があります。Google Maps Directions APIを使用して、利用可能な2つの家の間の歩行距離を計算し、リストを並べ替えて、近い2つの家を選択できるようにしたいと思います。

Googleが1日あたり2,500クエリの理論上の制限を設定していることを除いて、すべてがうまく機能します（実際には、制限ははるかに低く、1日あたりわずか250です）。300 ² /2-300 = 44,700のクエリを実行する必要があるため、この制限では明らかに不十分です。

これは1回限りのことですが、Google Maps APIで必要なことをどのように達成できるかについてのヒントはありますか？どういうわけか、制限が1つのインスタンスにのみ影響するように、分散されたプログラムを実行できますか？Google App Engineは役に立ちますか？

アルゴリズムを改善するためのアドバイスも歓迎します。2つの家が遠く離れていて、別の家が1つに近い場合は、おそらく遠く離れているため、残りの家で3番目の家をチェックする必要がないことを意味します。また、正確な距離ではなく、アルゴリズムの質的な性質に関心があるため、クエリが少なくなるような簡単な近似ができるかもしれません。

ありがとう、

Javaを使用して.osmマップ上の最短パスを見つけるための単純なダイクストラのアルゴリズムを実装しました。

.osmファイルから作成されたグラフのパスファインディングは非常にうまく機能します。しかし、ユーザーの現在の場所や目的地がこのグラフのノードではない場合（生の座標のみ）、パスファインディングを機能させるために、これらの座標をグラフに「リンク」するにはどうすればよいですか？

「現在のロケーションノードに最も近いものを見つけて直線を描く」という単純で単純な解決策は、現実的ではないようです。添付の写真のような状況になった場合はどうなりますか？（UPD）

ここでの問題は、「スマートな」パスファインディングアルゴリズム（ダイクストラのような）を開始する前に、現在の位置をグラフに「リンク」することですが、これは、地理的座標とこの式は「パスファインディング」ではありません-障害物やノードのタイプを考慮に入れることはできません。

言い換えると、Bがグラフのノードであり、Aがノードではない場合、AとBの間の最短経路をどのように見つけるのでしょうか。

この問題に対する他の解決策について聞いたことがありますか？

エッジの重みが負の有向グラフがあります。グラフはプログラムによって変更され、負のサイクルを形成することがあります。その場合、最短経路アルゴリズム (Bellman-ford/Johnson/Floyd-Warshall) は、そのような負のサイクルの存在を検出して失敗しますが、他の有用な情報は生成されません。

どのエッジが負のサイクルを引き起こしているのかを特定し、グラフでそのような変更を禁止したいと考えています。誰かがポインタで私を助けることができますか?

ありがとう、

ポール

8 つの方向のいずれかに移動できる正方形のタイルのマップがあります。隣接するタイルから別のタイルに移動するコストを示す関数が呼び出されcost(tile1, tile2)た場合、許容可能で一貫性のあるヒューリスティック関数 h(y, goal) をどのように見つけますか? costこの設定でヒューリスティックを見つける方法を一般化できますか、それとも機能 によって異なるのでしょうか?

ノードのグラフ (ネットワーク) があるとします。重み付けは次のとおりです。 1. 2 つのノード間のリンクを片道移動する。2. 2 つのノード間のリンクを逆方向に移動する (これらは異なる場合があります)。3. あるリンクから別のリンクへの変更。

また、一部のノードは一方向のみです。

この場合、次の場合に最適なアルゴリズムは次のとおりです。a) 最小スパニング ツリーを見つける b) 2 つのノード間の最短ルートを見つける c) 「巡回セールスマン」パス (つまり、どこにでも行き、重複を最小限に抑える最短ルート) を見つける?

また、双方向のものを、各方向に異なる重みを持つ双方向パスではなく、2 つの単方向パスとして扱うのが最善でしょうか?

- -例 - -

<2/3> は、左に移動する 2 と右に移動する 3 の重量を意味します。^1/4 は、1 が上に移動し、4 が下に移動することを意味します。2 つのリンク間の 1 つの数値は、リンクを変更するコストです。たとえば、AD から DF に移動するには 8 のコストがかかり、AB から BE に移動するには 2 のコストがかかります。

それが理にかなっていることを願っています...

サイモン

（ps悪い用語についてお詫びします-「リンク」、「エッジ」-好きなものなら何でも;））

重み付けの種類をよりよく説明するために、エッジが線路であり、ノードが駅であると想像してください。エッジのコストは 2 つの駅間の電車の移動時間であり、ノードのコストはインターチェンジ時間の長さです (プラットフォームがどれだけ離れているかによって、同じノードであってもエッジ間で異なる場合があります。サービスの定期性など）。