ダイクストラ法について

[テンペ]

下に示されるC言語の関数dijkstra(int s, int g)は、頂点sから頂点gまで到達可能な場合にはその2頂点間の最短距離を、到達不可能な場合には-1を返す関数です。ただし、ここで有効グラフにおける2頂点sおよびg間の最短距離を、頂点sから頂点gへ到達するまでにたどる矢印の最小数とする（重みが1ということ)
という問題で、

下記のコードの/A/部分がわかりません。//A//の文の数は分かりません。
node.distanceの値を更新するのかと思ったのですが、方法が思いつかないです。

コード:

int dijkstra(int s, int g){
　struct {
　int found;
　int distance;
  }NODE[N];

　int i,j,min;
　for(i=0;i<N;i++){
　　node[i].found=0;
　　node[i].distance=N;
}

node[s].distance=0;

for(j=1;j<N;j++){
　node[s].found=1;
　if(s==g)
return node[s].distance;

　　for(i=0;i<N;i++){
　//A//
　}

　min=N;
　　for(i=0;i<N;i++){
　　if(!node[i].found)
　　　if(node[i].distance<min){
　　　　min=node[i].distance;
　　　　　s=i;
　　}
　}
}
return -1;
}

[みけCAT]

提示されたコード中に「矢印」を表すと思われるデータが一切見当たらないので、わかりません。
ところで、どうしてコードが全くインデントされていないのでしょうか？

[みけCAT]

下記のコードの/A/部分がわかりません。//A//の文の数は分かりません。
node.distanceの値を更新するのかと思ったのですが、方法が思いつかないです。

そもそも、このコードには

• 5行目でセミコロンが抜けている
• Nが0以上だと仮定すると、8行目のループを抜けた時i=Nであり、そのまま15行目のループに行くので、jもNになり、
  (//A//を含む)15行目のループの中身は全く実行されない
• Nが0未満だと仮定すると、8行目のループを抜けた時i=0であり、そのまま15行目のループに行くので、jも0になり、
  (//A//を含む)15行目のループの中身は全く実行されない

という問題があるので、//A//だけを書き換えることでこの関数を完成させるのは無理だと思います。

[テンペ]

失礼しました。コードを訂正しました。15行目、iではなく1でした。

[かずま]

インデントが変です。
全角スペースは使用しないでください。

勝手にグラフを作ってやってみました。

コード:

#include <stdio.h>

#define N 8

int path[N][N] = {
    /* -> 0  1  2  3  4  5  6  7 */
    /*0*/ 0, 1, 1, N, N, N, N, N,
    /*1*/ N, 0, N, N, 1, N, N, N,
    /*2*/ N, 1, 0, 1, N, 1, N, N,
    /*3*/ N, N, N, 0, 1, 1, 1, N,
    /*4*/ N, N, N, N, 0, N, N, 1,
    /*5*/ N, N, N, N, N, 0, 1, N,
    /*6*/ N, N, 1, N, N, N, 0, 1,
    /*7*/ N, N, N, 1, N, N, N, 0,
};

int dijkstra(int s, int g)
{
    struct {
        int found;
        int distance;
    } node[N];

    int i, j, min;
    for (i = 0; i < N; i++) {
        node[i].found = 0;
        node[i].distance = N;
    }

    node[s].distance = 0;

    for (j = 0; j < N; j++) {
        node[s].found = 1;
        if (s == g)
            return node[s].distance;

        for (i = 0; i < N; i++) {
            if (!node[i].found) {
                int dist = node[s].distance + path[s][i];
                if (dist < node[i].distance)
                    node[i].distance = dist;
            }
        }

        min = N;
        for (i = 0; i < N; i++) {
            if (!node[i].found)
                if (node[i].distance < min) {
                    min = node[i].distance;
                    s = i;
                }
        }
    }
    return -1;
}

int main(void)
{
    int distance = dijkstra(0, 7);
    printf("0->7: %d\n", distance);
    return 0;
}

for (j = 1; のループは、for (j = 0; でないといけないのでは?

[かずま]

失礼しました。コードを訂正しました。15行目、iではなく1でした。

返信のついた質問を後から修正してはいけません。

なぜなら、後からこのトピックを読んだとき、返信の指摘が
正しいものかどうかわからず、読んだ人が混乱するからです。

修正は、新たな返信でお願いします。