4

mysqlの正規化された隣接リストを使用して加重グラフを設計しました。次に、指定された2つのノード間の最短パスを見つける必要があります。

私はPHPでダイクストラを使おうとしましたが、それを実装することができませんでした（私には難しすぎました）。私が感じたもう1つの問題は、ダイクストラを使用する場合、すべてのノードを考慮する必要があるということでした。これは、大きなグラフではおそらく非常に非効率的である可能性があります。それで、誰かが上記の問題に関連するコードを持っていますか？少なくとも誰かがこの問題を解決する方法を教えてくれたら素晴らしいと思います。私はここでほぼ一週間立ち往生しています。助けてください。

4

3 に答える 3

5

これはA*アルゴリズムの典型的なケースのように聞こえますが、ダイクストラを実装できない場合は、A*を強制することはできません。

ウィキペディアのA*

編集：これは、1つのノードから目標に到達するためのコストを見積もる（ただし、過大評価しないことが重要です）方法があることを前提としています。

edit2：隣接リストの表現に問題があります。マップ内の頂点ごとにオブジェクトを作成すると、リンクがあるときにこれらのオブジェクトに直接リンクできるようになります。つまり、基本的には、オブジェクトのリストになります。各オブジェクトには、隣接するノードへのポインター（または参照）のリストが含まれています。ここで、新しいノードのパスにアクセスする場合は、リンクをたどるだけです。無限のサイクルを回避するために、特定の頂点に対してたどったパスのリストを維持するようにしてください。

何かにアクセスする必要があるたびにDBにクエリを実行する限り、とにかくこれを実行する必要があります。必要な場合にのみDBをクエリすることをお勧めします...これは、グラフ内の特定のエッジ、またはグラフ内の1つの頂点のすべてのエッジに関する情報を取得する場合にのみDBをクエリすることを意味します（後者は可能性が高いです）より良いルートになります）、巨大なチャンクを一度にヒットするのではなく、遅いI/Oをたまにヒットするだけです。

于 2009-12-09T01:34:20.027 に答える
2

これは、Javaでのダイクストラアルゴリズムのリテラシーバージョンであり、PHPでそれを実装する方法を理解するのに役立つ可能性があります。

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

于 2009-12-09T01:33:45.690 に答える
2

ダイクストラアルゴリズムは、指定された頂点から他の頂点への最短経路を返します。
その擬似コードはWikiにあります。

しかし、DIRECTEDグラフ内のすべての頂点間の最短経路を見つけるFloydアルゴリズムが必要だと思います。

両方の数学的複雑さはかなり近いです。

どちらの場合も、WikiからPHPの実装を見つけることができました。

于 2009-12-09T01:40:47.047 に答える