問題タブ [shortest-path]

重み付きグラフGとその最短経路距離の行列デルタが与えられます。したがって、delta（i、j）は、iからjへの最短経路の重みを示します（iとjはグラフの2つの頂点です）。デルタは最初に最短経路の値を含めて与えられます。エッジEの重みが突然WからW'に減少します。O（n ^ 2）のdelta（i、j）を更新する方法は？（n =グラフの頂点の数）問題は、O（n ^ 3）の複雑さが最も高い全ペア最短経路を再度計算しないことです。問題はデルタの更新であるため、すべてのペアの最短パスを再計算する必要はありません。

より明確に：私たちが持っているのはグラフとそのデルタ行列だけです。デルタ行列には、最短経路の値だけが含まれます。次に、グラフの変更に応じてデルタ行列を更新します。エッジの重みが減少します。O（n ^ 2）で更新する方法は？

これが最大 L 合計に関する私の最初の質問です。

問題: mxnの 正の整数行列が与えられた場合、1 行目から m 行目までの L の合計の最小値を見つけます。L(4 項目) チェスの馬の動きが好き

例 : M = 3x3

0 1 2

1 3 2

4 2 1

可能な L の動きは次のとおりです: (0 1 2 2), (0 1 3 2) (0 1 4 2)

私はこれを動的プログラミングで解決しました。これが私のアルゴリズムです:

1. mxn の別の Minimum L Moves Sum 配列を取得し、メイン マトリックスの最初の行をコピーします。私はそれを (MLMS) と呼んでいます 2.最初のセルから開始し、L の動きを調べて計算し
ます 3.存在する値よりも小さい場合は MLMS に挿入します4.
ステップ2 を実行します. m 番目の行まで5.最小値を選択しますm行目の合計

私の例を段階的に説明しましょう：

1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 合計 (L2 = (0,1,3,2)) = 6; したがって、MLMS[ 0 ][ 1 ] = 6
   sum(L3 = (0, 1, 3, 2)) = 6 ; 合計 (L4 = (0,1,4,2)) = 7; したがって、MLMS[ 2 ][ 1 ] = 6
   

2. M[ 0 ][ 1 ] sum(L5 = (1, 0, 1, 4)) = 6; 合計 (L6 = (1,3,2,4)) = 10; したがって、MLMS[ 2 ][ 2 ] = 6
   

   ... 最後の MSLS は次のとおりです。
   0 1 2
   4 3 6
   6 6 6
   これは、6 が 0 から m まで到達できる最小 L 合計であることを意味します。

O(8*(m-1) n) = O(m n)だと思います。この問題に適合する最適なソリューションまたは動的計画法アルゴリズムはありますか?

ありがとう、長い質問でごめんなさい

ヘッドノードからテールノードまでのグラフからノードの最短シーケンスを見つけるアルゴリズムがあるかどうか知りたいです。グラフはヘッドノードから分岐し、任意に複雑で、テールノードに収束します。ノード間のすべての接続は重み付けされていません。

頭と尾のノードから、グラフの両端のノードが接触するまで、この問題に取り組むことを検討していますが、「より良いホイール」が存在するかどうかを（再）発明する前に知りたいです。 。

ダイクストラまたはベルマンフォードのアルゴリズムを使用して、特定の頂点に移動した場合にエッジの一部が影響を受けるグラフの最短経路を見つけるにはどうすればよいでしょうか。そのため、影響を受けるエッジの長さは、元の長さよりも長くなったり短くなったりします。

私は私が持っているいくつかの仕事で少し助けを探しています。

タスクは、ロンドン地下鉄の旅のプランナーを作成することです。

編集：-

現時点では、HashTableにエッジデータを持つノードの隣接リストがあります。

幅優先探索を使用して、任意の2つの頂点間の最短経路を取得する方法を見つけたいと思います。

チューブマップのように、頂点は論理的に接続されています。各ステーションのエッジは、次を使用して表されます：（this_station、next_station、tube_line）<-これは、各ステーションについて私が持っている情報です。

これをトラバースするのは非常に注意が必要です。どんな助けでも真剣に感謝します！

3 つのシャトル ルートのコスト (各駅間の距離) を含む有向グラフを作成済みです。どのシャトル路線でも駅から駅までの運賃は同じなので、乗り換えを最小限に抑えるしかありません。

私はそれがこのように機能することを望みます。駅 A -> C から行きたいと思います。簡単のため、最初に駅間の距離を 1 と仮定します。

ルート 1 とルート 2 の両方に A -> C のパスがあるため、コストが最も低いルート 2 を選択します。これは既に実行済みです。

しかし、駅 C -> Y から行きたい場合、C -> Y からの直接ルートはありません。したがって、1 または 2 から行き、A で降りて、A -> Y から行く必要があります。基本的には、シャトルの乗り換えと移動距離を最小限に抑えたい。

これには一般的なアルゴリズムがありますか?

私はアカデミック プロジェクトに取り組んでいます。大規模で重み付けされた有向グラフの最短経路を見つけるためのライブラリを作成しています。

仕様は次のとおりです。

• サンプル データ セットは、ノードあたり平均 5.68 エッジの 1500 頂点のグラフです。仕様は最大 20.000 ノードまで異なる場合があります。

• さらに、私はCPU /メモリバウンドの環境で作業しています：Android。

• エッジの重みは自明ではなく、一定でもありません。グラフの変数の状態に依存します。

• オフラインで作業する必要があります。

私はいくつかの困難に直面しています：

• グラフのデータを効率的に保存、取得、更新する方法が必要です。Java クラスからのクエリで SQLite オブジェクトを使用する必要があるか、ヒープ上の大きなカスタム Java オブジェクトを使用する必要がありますか? これはパフォーマンスにとって最も重要な側面だと思います。

• ある種のショート パス アルゴリズムを効率的に実装する方法が必要です。すべての重みが正であるため、訪問したノードのコンテナーとして ArrayList を使用して Dijikstra アルゴリズムを適用する必要がありますか?

• これは NDK を使用する良いケースですか? このタスクは CPU を集中的に使用しますが、メモリへのアクセスも頻繁に行うため、そうではないと思いますが、貢献することはできます。

• リソースが不足していること、RAM が不足していること、ディスクが遅いこと、CPU が貴重であることを常に覚えておいてください (バッテリーに関して)。

どんなアドバイスでも大歓迎です、乾杯:)

最短経路問題（または他のグラフ理論の問題）のデータを表示・編集するためのグラフィカルツールが必要なのですが、このツールを知っている人はいますか？

Djikstra の最短経路のようなものを使用して、Python で運転方向を実装したいと考えています。このアルゴリズムでは、データをグラフ構造で表す必要があります。生の GIS データ (シェープ ファイルやOpenStreetMap データなど) は、データの表現方法が異なります。したがって、GIS データをグラフ構造に変換できる Python ライブラリはあるのでしょうか?

Java では、GeoTools がまさに私が説明したものを持っていることがわかりました。Python に同様のライブラリはありますか?

2 つの異なる場所 (座標) 間の最短距離を見つけるために、matlab アプリケーションに Google マップ API を埋め込みたいと考えています。ポリラインを表示してみました。

matlab でこれを達成するにはどうすればよいですか?

ありがとうございます