問題タブ [dijkstra]

C での A* 実装はどこにありますか?

私は周りを見回していましたが、私のgoogle-fuは十分に強力ではないようです. 独自の実装を書き始めましたが、Stack Overflow を思い出し、最初にここで質問する必要があると考えました。実際の A* 実装を作成するのは少し複雑に思えます - バイナリ グリッド用の Dijkstra のアルゴリズムの実装だけを作成したくなりましたが、それが本当に必要なためです。レパートリー。

私はCodersatWorkを読んでいます。

私はドナルド・クヌースのインタビューでこの段落に出くわしました。

Seibel：私が話をした多くの人々は、彼らが始めたとき、マシンに直接アクセスしていたようです。それでも、ダイクストラはあなたが精通していると確信している論文を持っています。彼は基本的に、コンピュータサイエンスの学生にトレーニングの最初の数年間は機械に触れさせてはならないと言っています。シンボルの操作にすべての時間を費やす必要があります。

その論文へのリンクが欲しい。それはどの紙ですか？（彼はあまりにも多くを書いた:-)

過去 4 日間、私はダイクストラのアルゴリズムを理解しようとしています。しかし、私はできません。ポイントのベクトルがあります。そこから、コスト マトリックスを作成しました。しかし、ダイクストラのアルゴリズムの作り方がわかりません。ソースはネットで入手できますが、私はコンピュータ サイエンスのバックグラウンドを持っていないため、理解できません。私はこのような機能を作ろうとしています

誰かがあれば、コードを投稿してください。私は怠け者ではありません。しかし、私のプロジェクトは 1 日前にすでに締め切りを過ぎていました。今、私は論理を理解するという希望を失いました. 今は機能が欲しいだけです。「困っている人はまさに天使です」 .

編集：「Loki astari」の優れた回答に感謝します

プログラムでダイクストラアルゴリズムを使用しています。頂点とエッジのあるグラフがあるとします。ソース頂点「a」から始まるすべてのエッジを想像すると、次のようになります。

頂点「f」で終わるすべてのエッジは次のとおりです。

最初から知っておく必要があるのは、エッジa- > bを開始エッジ（開始点として「a」を想定）にしたいので、 「a」の他のネイバーを検索する必要がないということです。(a-->c and a-->d)

また、 m-> fで終わるパスのみが必要です（宛先として「f」を想定）。つまり、次のようなパスは必要ありません。b-->f,m-->f,e-->f,w-->f

それで、これらのエッジを含まないように最初のグラフをトリミングしてから、それにダイクストラを適用するのは良い考えですか？

実際にこれらのエッジを見つけるには、いくつかの検索が必要です。（時間やCPU使用率を考慮して）検索を実行してグラフをトリミングする価値があるのでしょうか、それとももっと良い方法があるのでしょうか。

バスのルートを見つけることができるオフライン C# アプリケーションに取り組んでいます。時刻表/バス/路線データを抽出できます。基本データで機能する最も単純なソリューションを探しています。

バス停「A」からバス停「B」までの経路を見つけるために使用できるアルゴリズムは? C#/Java に対応したオープンソース ソリューションはありますか? データベースの Google GTFS 形式は単純なソリューションに適していますか? http://code.google.com/transit/spec/transit_feed_specification.html

助けてくれてありがとう。私はこれで立ち往生しています。どこから始めればいいのかわからない - データを保存する方法とルートを見つける方法。Dijkstra/A* については知っていますが、時間に依存しないグラフでのみ使用しました...

Cでのダイクストラのアルゴリズムについて助けが必要です。

次のような隣接行列を生成しました。

私はこの実装を見つけました：http ：//www.answers.com/topic/dijkstra-s-algorithm-1しかし、パスは1次元配列であり、私のマトリックスは2次元配列です。

あるものを別のものに変換する方法はありますか？あるいは、誰かがこの種の行列を処理する方法を持っているかもしれません。

助けてくれてありがとう

「アルゴリズムの概要、第3版」の演習24.3-5では、これが間違っている（常に正しいとは限らない）例が必要です。それは可能ですか？私の考えでは、現在の頂点へのパスがすでに決定されているときにすべてのエッジが緩和されるため、これは不可能です。

一言一言：

N教授は、ダイクストラのアルゴリズムが正しいことを証明していると主張しています。彼は、ダイクストラのアルゴリズムは、グラフ内のすべての最短パスのエッジを、パスに表示される順序で緩和するため、パス緩和プロパティは、ソースから到達可能なすべての頂点に適用されると主張しています。ダイクストラのアルゴリズムが最短経路のエッジを順不同に緩和できる有向グラフを作成して、教授が間違っていることを示します。

ダイクストラアルゴの配列ベースのバージョンを使用する（実装しない）必要があります。タスクは、一連の線分（障害物）と開始/終了ポイントを指定して、開始/終了ポイントから最短パスを見つけて描画する必要があることです。計算部分などを行ったが、私のコードでダイクストラを使用する方法がわからない。私のコードは次のとおりです。

これで、各セグメントから他のすべてのセグメントまでの距離がわかりました。このデータを使用してamd（neighbourinfo内）配列ベースのダイクストラ（制限）を使用して、開始点/終了点からの最短経路をトレースします。コードは他にもありますが、読者の使いやすさのために問題を短縮しました

助けてください!!私はコアC++のみを使用しているので、ありがとうとplz no .net lib/code..事前に感謝します

しかし、配列ベースのバージョンが必要です（厳密には..）他の実装を使用することは想定されていません。

両方を使用して、単一のソースから最短パスを見つけることができます。BFS は で実行されますO(E+V)が、ダイクストラは で実行されO((V+E)*log(V))ます。

また、ダイクストラがルーティング プロトコルとよく似た方法で使用されているのを見てきました。

では、BFS が同じことをより高速に実行できるのに、なぜダイクストラのアルゴリズムを使用するのでしょうか?

インタビューでこの質問をされたのですが、まともな答えが思いつきませんでした。そこで、すべてのサイクルを見つけてから、最も短いサイクルを選ぶという素朴なアプローチを彼らに伝えました。

この問題の効率的な解決策を知りたいです。