アップデートにおけるプリムアルゴリズムとダイクストラアルゴリズムの違い



Difference Between Prim Algorithm



プライム:

visit[index] = true//Another point corresponding to the shortest side is included in the set cout << index << ' ' sum += minor//The total distance length of the smallest tree for (int j = 0 j if (!visit[j] && dist[j]>g[index][j]){//The update currently includes the previously connectable points (the shortest). The current distance between this point a and other points b may be shorter than the distance between other points c and b before, so it needs to be updated. dist[j] = g[index][j] } }

ダイクストラ:



s[u] = true for (int j = 1 j <= n j++) {//Update the previous distance to v0 from the point of the smallest side if (!s[j] && dist[u] + map[u][j] map[u][j] pre[j] = u//If there is a smaller side, then the predecessor of j is u } }

私もこのことを学び始めたばかりです。それを読んだ後、私は2つのアルゴリズムがまったく同じであることに気づきました。プリムアルゴリズムは、最小接続値を見つけるための最小スパニングツリーを計算するために使用され、ダイクストラアルゴリズムは、単一ソースの最小パスを作成するために使用されます。違いは、更新配列の位置にあります。 Primは、セットに追加されたすべてのポイントから追加されていないポイントまでの最小距離を更新します。これにより、引き続きポイントが含まれます。
ダイクストラの更新は、最初のポイントからすべてのポイントまでの最小距離を参照します。当然、原点からこの点までの距離+この点から目標点までの距離は、原点に直接接続するために必要です。目標点の距離が判断されます。次に、最短距離を更新します。要約すると、私が理解しているアップデートには非常に多くの違いしかありません。私の説明はとても簡単です。それを深く理解したい場合は、アルゴリズムの証明と派生プロセスを注意深く研究する必要があります。