問題タブ [dijkstra]

私は今日、 「The Humble Programmer」を楽しんでいて、次の引用に出くわしました。

したがって、しばらくの間、おそらく永遠に、第 2 種の規則は、プログラマーに必要な規律の要素として現れます。私が念頭に置いているルールのいくつかは非常に明確であるため、教えることができ、特定のプログラムがルールに違反しているかどうかについて議論する必要はありません。例としては、終了の証明を提供することなく、または繰り返し可能なステートメントの実行によって不変性が破壊されない関係を述べることなく、ループを書き留めてはならないという要件があります。

私は、ダイクストラの 1300 以上の著作の中で、彼が上で説明した規則をさらに詳細に説明しているのに最も適したものを探しています。

私は、パスファインディングの形式を実装するように任命されました（コースワーク@大学）。さて、仕様では、検索するノードの数に制限があるため、ブルートフォースを実装することもできます（最初、途中で2つ、最後）が、このコードを再利用して、ダイクストラを実装するようになりました。アルゴリズム。

私はウィキペディアで疑似を見たことがあり、友人も私のためにいくつか書いていますが、それは意味がありません。アルゴリズムは非常に単純に見え、それを理解することは私にとって問題ではありませんが、私はそのようなことを実現するコードを視覚化することはできません。

何か提案/ヒントはありますか？

いくつかの混乱のために編集してください：
はい、ターゲットノードとソースノードがあります。
後でコードを再度使用したいので、「2つの中間停止のみ」の場合ではなく、一般的な場合にダイクストラを実装しようとしています。それ以外の場合は、ブルートフォース実装を作成するだけです。
私が少し問題を抱えている特定の問題は、それらが最適になる可能性がある場合に備えて、次善の半分の形式のパスを保存することです。特定のノードにアクセスしているときに、そのノードを通過するすべての接続を更新する方法がわかりません。
さらに編集：
今すぐいくつかの答えを調べて、試してみてください。

本当に編集：深刻な問題について言及するのを忘れました。これは、任意の2つの頂点間で最大UINT_MAXの異なる距離を持つことができるということです。ごめん。実際、私がこれに対処するのを忘れたという事実は、おそらくそもそもひどい問題の原因ですが、解決策は、幸いなことに、最短のものを選ぶことは私には明らかです。他の人の距離変数の疑似が私の可変距離を考慮していなかったのも不思議ではありません。

次のグラフデータをデータベースに保存したいのですが、

次に、WebサーブレットからDijskraアルゴリズムを実行して、保存されているグラフデータを使用して最短経路計算を見つけます。次に、サーブレットからhtmlファイルへのパスを出力します。

問題は、BNF で指定されたような入力関数があるとsin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)します。再帰降下アルゴリズムを使用して入力を解析し、ダイクストラのアルゴリズムを使用または変更して、この特定の関数を処理するにはどうすればよいでしょうか? sin | で実行する必要があります。コス | 平方根 | ln では、ダイクストラのアルゴリズムが作業を行う必要があります。

編集:私も尋ねるべきかもしれません:特定の機能を表すためのベストプラクティスまたはデータ構造は何ですか?

EDIT：入力セットは次のように取得できます：

編集: Shunting Yard は、入力関数を RPN に変換するアルゴリズムですが、sin | のような別の関数を受け入れるように拡張するにはどうすればよいですか? コス | 平方根 | ん？再帰降下は、Shunting Yard に必要な拡張を提供しますか?

最近、ダイクストラのアルゴリズムの 1 つ ( shunting-yard )について質問しました。しかし、ほとんどの人は、「ダイクストラのアルゴリズム」は彼の最短経路アルゴリズムを意味すると考えていました。

ダイクストラが開発した他のアルゴリズムは何ですか?

巨大なグラフ内のノード間の最短経路をリアルタイムで見つける方法を探しています。数十万の頂点と数百万のエッジがあります。この質問は以前に尋ねられたことを知っており、答えは幅優先検索を使用することだと思いますが、それを実装するために使用できるソフトウェアを知りたいと思っています。たとえば、無向グラフで bfs を実行するためのライブラリ (python バインディング付き!) が既に存在する場合、それは完全に完璧です。

このコードは、アルゴリズム設計マニュアルの本から作成したコードですが、ポインタの経験がほとんどないため、コンパイルできません。これが、コンパイルできない主な理由だと思います。

そして、誰かがdjikstraを少し変更して、現在の構成でヒープを通過できるようにすることができれば。

Why can't we apply Dijkstra's algorithm for a graph with negative weights?

グラフは重み付けされておらず、HashSets neighbours[] の配列の要素はノード neighbours[1] はノード 1 (0 から始まることに注意してください) であり、一意の隣接ノードは 2 3 4 5 となります (したがって、neighbours[5] 1) が含まれます。そして、理論をはるかに超えるアルゴリズムを取得できないため、多大な助けを借りて行った次の方法があります。返される数値は、グラフ内の 2 つのノード間の平均距離である必要があります。

次のグラフがあると想像してください (ノード: in_links | out_links; neighbours[] には、ノード 0 に 0 ループが含まれておらず、前述のように重複もありません。)

そして、この自明なグラフでは、返される距離は 5.781686749230769E8 ?!?! です。コード：

私は実数のキャストや印刷の経験があまりないので、それらと関係があることを願っています! すべてのコメントを歓迎

問題は次のとおりです。5 つの頂点を持つ有向グラフを考えてみましょう。図 1 に示すように、ダイクストラのアルゴリズムがノード s から他のすべてのノードへの最短経路を生成するとします。エッジ (x, t) の重みを増やし、すべてのノードが何らかの方法でこの情報を取得すると仮定します。ノード s はダイクストラのアルゴリズムをどのように変更して再計算を最小限に抑えますか? 「ノード s は、S を として初期化し、リスト (< 各ノード >) を として維持することにより、ダイクストラのアルゴリズムを実行する」という形式で最終的なソリューションを提供します。</p>

私の質問は... s から t への最短経路を増やすだけなので、それはひっかけ問題ではありませんか?

よし、私の写真は機能していない

しかし、それは次のように機能します：

s->y->x->t

y は z も指します。y->z

これらは一方向矢印です。