14

タイトルが言ったように、私は与えられたグラフのノードのすべてのペア間の距離を見つけるアルゴリズムを実装しようとしています。しかし、もっとあります:(あなたを助けるかもしれないもの）

  • グラフは重み付けされていません。すべてのエッジの重みが1であると見なすことができることを意味します。
  • |E| <= 4*|V|
  • グラフはかなり大きいです（最大で約144の深さ）
  • グラフは
  • サイクルがあるかもしれません
  • 私はPythonでコードを書いています（アルゴリズムを参照する場合は、コードもいいでしょう:)）

ジョンソンのアルゴリズム、フロイド-ワーシャル、およびすべてのペアのダイクストラについて知っています。ただし、これらのアルゴリズムは、グラフに重みがある場合に適しています。

これらのアルゴリズムは重み付きグラフを対象としているため、私の場合により良いアルゴリズムがあるかどうか疑問に思いました。

ありがとう！

4

10 に答える 10

11

重み付けされていないグラフでは、重み付けされたグラフには当てはまらない追加の属性が得られるため、改善の余地があります。

AからCに直接接続しているエッジの場合、3番目のノードBを経由する短いパスがないことは確かです。

これを念頭に置いて、ダイクストラのアルゴリズムを単純化できるはずです。ご存知かもしれませんが、これは3セットのノードで機能します。

  1. 決定的な最短経路が知られているもの、
  2. 予備距離が計算されたものと
  3. まだ調査されていないもの。

（1.）からe（ 3.）へのエッジをたどる場合、元のダイクストラはノードを（3.）から（2.）に移動します。上記の属性はすべてのグラフに当てはまるため、セット（1.）に直接追加できます。これはより効率的です。ACC

重要な観察事項は次のとおりです。上記の手順は基本的にBFS（幅優先探索）です。つまり、のある固定ノードvから他のノードまでの距離を見つけることができますO(|V| + |E|)。

元の質問では、グラフは基本的にいくつかの穴のあるグリッドであるとは述べていませんでした。これはさらに強力な要件であり、これを利用できると確信しています。「グリッドグラフ最短経路」をすばやく検索すると、最良の場合に有望なこの論文が得られます。O(sqrt(n))あなたが指定する問題はかなりよく構造化されているので、あなたが調べたいと思うかもしれないいくつかの論文がもっとあると私はほぼ確信しています。

于 2011-05-01T20:36:07.797 に答える
9

各ノードから幅優先探索を実行します。合計時間：O（| V | | E |）= O（| V | 2）、これは最適です。

于 2011-05-01T21:10:25.017 に答える
1

すべてのエッジが重み付けされていない場合に距離を測定する方法はわかりませんが、EdmondのBlossomVアルゴリズムを確認したいと思います。http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphsを確認します。これは似たようなものです：http ：//wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html 。

于 2011-05-01T20:30:32.480 に答える
1

次の非常に単純な実装で、ウォーシャルアルゴリズムはどうですか。

def warshall(graph):
  n = graph.numNodes+1
  W = [ [graph.w(i,j) for j in graph.V()] for i in graph.V() ]
  for k in range(1,n): 
    for i in range(1,n):
      for j in range(1,n):
        W[i][j] = min( W[i][j] , W[i][k]+W[k][j] )
  return W

どこ

  • V()グラフのすべての頂点を生成します
  • w(i,j)エッジの重み（i、j）を生成します-あなたの場合、すべて1または0
  • numNodesグラフのノードの数を生成します。

ただし、複雑さはO（n ^ 3）です。

于 2011-05-01T21:09:49.480 に答える
1

高岡忠雄による「全ペア最短経路問題のサブキュービックコストアルゴリズム」を参照してください。単位重量（実際には最大エッジ重量= O（n ^ 0.624））のグラフに対して、サブキュービックの複雑さを持つシーケンシャルアルゴリズムが利用可能です。

于 2011-05-02T00:46:08.563 に答える
1

グラフは動的であると想定しています。それ以外の場合は、このような小さなグラフですべてのペアの距離を事前計算するためにFloyd-Warshallを使用しない理由はありません;）

0 <= x <= n、0 <= y <= nの点（x、y）のグリッドがあるとします。エッジE：（i、j）<->（i + 1、j）を削除したら、行jをセットA = {（0、j）、...、（i、j）}、B=に分割します。 {（i + 1、j）、...、（n、j）} Aのポイントa、BのbがEの周りをルーティングするように強制されるため、すべてのペア（a、b）の距離を再計算するだけで済みます。 （A、B）で。

たぶん、Floyd-Warshallを事前計算し、このようなものを使用して、グラフの変更ごとに再計算をO（n ^ 2）（またはそれくらい）に減らすことができます...

于 2011-07-05T22:20:08.163 に答える
1

networkxを試してみることをお勧めします。1000ノードで正常に動作するようです。

次のリンクには、重み付けされていないグラフの最短経路アルゴリズムが含まれています。

http://networkx.lanl.gov/reference/algorithms.shortest_paths.html

これは10ノードの例です。

from random import random
import networkx as nx
G=nx.DiGraph()
N=10
#make a random graph
for i in range(N):
    for j in range(i):
        if 4*random()<1:
            G.add_edge(i,j)

print G.adj
print nx.all_pairs_shortest_path(G)
print nx.all_pairs_shortest_path_length(G)

#output:
#Graph ADJ={0: {}, 1: {}, 2: {}, 3: {0: {}, 2: {}}, 4: {}, 5: {0: {}, 3: {}, 4: {}}, 6: {0: {}, 1: {}, 4: {}}, 7: {2: {}, 4: {}, 6: {}}, 8: {1: {}}, 9: {2: {}, 5: {}}}
#PAIRS={0: {0: [0]}, 1: {1: [1]}, 2: {2: [2]}, 3: {0: [3, 0], 2: [3, 2], 3: [3]}, 4: {4: [4]}, 5: {0: [5, 0], 2: [5, 3, 2], 3: [5, 3], 4: [5, 4], 5: [5]}, 6: {0: [6, 0], 1: [6, 1], 4: [6, 4], 6: [6]}, 7: {0: [7, 6, 0], 1: [7, 6, 1], 2: [7, 2], 4: [7, 4], 6: [7, 6], 7: [7]}, 8: {8: [8], 1: [8, 1]}, 9: {0: [9, 5, 0], 2: [9, 2], 3: [9, 5, 3], 4: [9, 5, 4], 5: [9, 5], 9: [9]}}
#LENGTHS={0: {0: 0}, 1: {1: 0}, 2: {2: 0}, 3: {0: 1, 2: 1, 3: 0}, 4: {4: 0}, 5: {0: 1, 2: 2, 3: 1, 4: 1, 5: 0}, 6: {0: 1, 1: 1, 4: 1, 6: 0}, 7: {0: 2, 1: 2, 2: 1, 4: 1, 6: 1, 7: 0}, 8: {8: 0, 1: 1}, 9: {0: 2, 2: 1, 3: 2, 4: 2, 5: 1, 9: 0}}
于 2011-07-12T09:54:47.877 に答える
0

Python Graphプロジェクトの場合：

http://code.google.com/p/python-graph/

ヒントヒューリスティックをサポートするA*アルゴリズムの私の実装を見つけることができます。ヒントアルゴリズムはピトグラスの定理以上のものである必要はないため、これは2次元での障害物回避に特に適しています。

私はこれがあなたが必要とするすべてをするだろうと思います。このプロジェクトで使用されるグラフの抽象化が気に入らない場合は、アルゴリズムを再利用できます。それは非常に一般的な方法で書かれています。

于 2011-05-09T08:58:21.323 に答える
0

アルゴリズム設計マニュアルをざっと読んだ後、Skienaが言わなければならないことは次のとおりです（第15.4章-最短経路から）。当然のことながら、多くの人がすでに提供しているのと同じ結論に達しますが、他のいくつかの洞察も提供します

最短経路を見つけるための主要なアルゴリズムは、ダイクストラのアルゴリズムです...

グラフは重み付けされていますか、それとも重み付けされていませんか？グラフが重み付けされていない場合、ソース頂点から開始する単純な幅優先探索により、線形時間で他のすべての頂点への最短経路が見つかります...

彼はあなたが興味を持っているかもしれない他のケース（例えば、入力が幾何学的な障害物のセットである場合はどうなりますか？すべてのポイントのペア間の最短経路が必要ですか？）に言及し続けますが、これらのケースでも彼はあなたと同じ結論を出します持っている：DjikstraのアルゴリズムまたはFloyd-Warshallアルゴリズム。

用途によっては、到達可能性を処理する推移閉包を調べて、同様のアルゴリズムを使用することもできます。

于 2011-07-12T16:14:31.580 に答える
0 
def from_vertex(v, E):
    active = [v]
    step = 0
    result = {v:0}
    while active:
        step += 1
        new_active = []
        for x in active:
            for nh in E[x]:
                if nh not in result:
                    new_active.append(nh)
                    result[nh] = step + 1
        active = new_active
    return result

基本的に、各頂点からフラッドフィルを実行し、その結果、その頂点から到達可能な他の頂点の最小距離を取得します。

于 2011-07-12T17:01:49.593 に答える