12

私はDijkstaのアルゴリズムのこの実装を作成しました。これは、ループの各反復でwhile Q is not empty、キューの最小要素を見つける代わりに、キューの先頭を取ります。

これが私が書いたコードです

#include <stdio.h>
#include <limits.h>

#define INF INT_MAX
int N;
int Dist[500];
int Q[500];
int Visited[500];
int Graph[500][500];

void Dijkstra(int b){
     int H = 0;
     int T = -1;
     int j,k;

Dist[b] = 0;

Q[T+1] = b;
T = T+1;

while(T>=H){
    j = Q[H];
    Visited[j] = 1;
    for (k = 0;k < N; k++){
        if(!Visited[k] && Dist[k] > Graph[j][k] + Dist[j] && Graph[j][k] != -1){
            Dist[k] = Dist[j]+Graph[j][k];
            Q[T+1] = k;
            T = T+1;
        }
    }

    H = H+1;
}
}  

int main(){

int src,target,m;
int a,w,b,i,j;

scanf("%d%d%d%d",&N,&m,&src,&target);

for(i = 0;i < N;i ++){
    for(j = 0;j < N;j++){
        Graph[i][j] = -1;
    }
}

for(i = 0; i< N; i++){
    Dist[i] = INF;
    Visited[i] = 0;
}


for(i = 0;i < m; i++){
    scanf("%d%d%d",&a,&b,&w);
    a--;
    b--;
    Graph[a][b] = w;
    Graph[b][a] = w;
}

Dijkstra(src-1);


if(Dist[target-1] == INF){
    printf("NO");
}else {
    printf("YES\n%d",Dist[target-1]);
}

return 0;
}

私はこれまでに見つけたすべてのテストケースに対してこれを実行しましたが、正しい答えが得られました。
私の質問は、なぜ分を見つける必要があるのか​​ということです。誰かがこれを平易な英語で私に説明できますか？また、コードが間違っていることを証明するテストケースが必要です。

4

4 に答える 4

3

このサンプルを見てください：

1-(6)-> 2 -(7)->3
  \          /
   (7)     (2)
     \    /
       4

つまり、1から2までの長さ6のエッジ、2から3までの長さ7のエッジ、1から4までの長さ7のエッジ、4から3までのエッジがあります。アルゴリズムでは、1から3までの最短パスの長さが考えられます。 13から2ですが、実際の最良の解決策は長さ9から4です。

これがそれを明確にすることを願っています。

編集：申し訳ありませんが、この例はコードにブレーキをかけませんでした。これを見てください：

8 9 1 3
1 5 6
5 3 2
1 2 7
2 3 2
1 4 7
4 3 1
1 7 3
7 8 2
8 3 2

出力はYes 8です。パスは7つしかかかりませんが、ここにideone1->7->8->3のリンクがあります

于 2013-01-04T15:01:46.963 に答える
2

あなたのコードは間違った時間計算量を持っていると思います。コードは（ほぼ）ノードのすべてのペアを比較しますが、これは2次の時間計算量です。

10000エッジの10000ノードを追加して、コードが1秒以内に実行できるかどうかを確認してください。

于 2013-01-04T15:06:18.900 に答える
2

最小距離で未訪問の頂点を見つけることは常に必須です。そうしないと、少なくとも1つのエッジが間違ってしまいます。たとえば、次の場合を考えてみましょう

4 4
1 2 8
2 4 5
1 3 2
3 2 1

             (8)   (5)
           1-----2----4
            \   /  
          (2)\ / (1) 
              3

そして私たちはvertex 1

distance[1]=0

あなたが訪問したときあなたvertex 1はリラックスvertex 2しvertex 3 たので今

distance[2]=8とdistance[3]=2

この後、最小値を選択vertex 2せず​​に代わりに選択すると、次のようになります。

distance[4]=13

vertex 3次に、どちらが得られるかを選択します

distance[2]=3

したがって、私たちはdistance[4]=13どちらがすべきだったのかで終わります

distance[4]=8

したがって、ダイクストラの各段階で未訪問から最小値を選択する必要があります。これは、を使用して効率的に実行できますpriority_queue。

于 2020-06-13T17:06:23.367 に答える
0

次のグラフのアルゴリズムを実行する場合、それは子の順序によって異なります。1から4までの最短経路を探しているとしましょう。

反例

1でキューから開始する場合。

dist[1] = 0
dist[2] = 21
dist[3] = 0

seen = {1}キューがプッシュされている間、キュー2から23を消費すると、、、dist[4] = 511 seen={1,2}2q = [に,なり、次にキューから消費された,3,4]ときに、すでにキューに追加されることはありません。したがって、アルゴリズムは後でパスからの距離を12 + 31 = 43に更新しますが、最短パスは32であり、オンになっています。32seen1->3-5->41->3->2->4

コード例を使用して、他のいくつかの側面について説明します。(u,v,w)ノードuに重みが付けられ、重みが付けられたエッジがあるv場所の接続リストがあるとしますw。そして、以下のようにグラフとエッジを準備しましょう。

graph, edges = {i: set() for i in range(1, N+1)}, dict()
for u,v,w in connection_list:
    graph[u].add(v)
    edges[(u,v)] = w

ALGORITHM1-訪問していない場合は、追加する子供を選択してください

q = deque([start])
seen = set()
dist = {i:float('inf') for i in range(1, N+1)}
dist[start] = 0

while q:
    top = q.pop()
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        if v not in seen:
            q.appendleft(v)

これはすでに上で説明されており、1と4の間の最短パスに対して32ではなく43の誤った結果が得られます。

問題は、キューに2を再度追加しないことでした。それから、子と子を再び削除しましょうseen。

ALGORITHM2-すべての子を再びキューに追加します

while q:
    top = q.pop()
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        q.appendleft(v)

これはその場合に機能しますが、この例でのみ機能します。このアルゴリズムに関する2つの問題、

  1. 同じノードを再度追加するため、より大きな例では、複雑さはEノードの数ではなくエッジの数に依存しV、密グラフの場合はと仮定できO(E) = O(N^2)ます。
  2. グラフにサイクルを追加すると、停止するチェックがないため、永久に実行されます。したがって、このアルゴリズムは循環グラフには適していません。

そのため、線形検索で最小の子を選択するために余分な時間を費やす必要があり、上記と同じ複雑さになります。ただし、優先キューを使用すると、最小検索を。O(lgN)の代わりに減らすことができますO(N)。これがコードの線形検索の更新です。

ALGORITHM3-線形最小検索を使用したダーティダイクストラのアルゴリズム

q = [K]
seen = set()
dist = {i:float('inf') for i in range(1, N+1)}
dist[start] = 0

while q:
    min_dist, top = min((dist[i], i) for i in q)
    q.remove(top)
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        if v not in seen:
            q.append(v)

これで、次回はヒープを使用して最適なダイクストラのアルゴリズムを使用することを覚えておくことができる思考プロセスがわかりました。

于 2020-07-10T22:26:02.983 に答える