各頂点に関する最短経路を求めたい

Question

実現したいこと

それぞれの頂点からの最短経路をダイクストラ法により出力したい

発生しているエラー

エラーはありません

対象のソースコード

#include<stdio.h>
#define max 1000000
#define N 7

void print_matrix(int a[][N]);

int main(void){
 
  int distance[N],visited[N],route[N],count_t[N];
  int i,j,k,count,min,now,temp;
 
  int matrix[N][N] = {
    { 0 , 17,max,max,max,max,max},
    { 17, 0 , 21, 7 ,max,max,max},
    {max, 21, 0 , 13, 5 ,max,max},
    {max, 7 , 13, 0 ,max, 5 ,max},
    {max,max, 5 ,max, 0 , 16, 22},
    {max,max,max, 5 , 16, 0 , 25},
    {max,max,max,max, 22, 25, 0 }};
 
  for(i=0;i<N;i++){
    visited[i] = 0; distance[i] = max; route[i] = -1 ; count_t[i] = 0;
  }
 
  print_matrix(matrix);
 
  //初期化を行う
  visited[0] = 1;distance[0] = 0;
  now = j = k = 0; min = max;

  for(j = 0;j <  5;j++){

    printf("---------------------------------------------------------------\n");
    printf("now = %d\n",now);
    count_t[j] = now; 
    for(i=0;i<N;i++){
      printf(" %6d ",distance[i]);
    }
   
    printf("\n");
   
    for(i=0;i<N;i++){
      printf(" %6d ",visited[i]);
    }
   
    printf("\n");
   
    for(i=0;i<N;i++){
      printf(" %6d ",route[i]);
    }
   
    printf("\n");

    // visited[now] = 1;
    for(i=0;i<N;i++){
    if(matrix[now][i] < max && visited[i] ==0 && matrix[now][i] > 0){
      // distance[i] = matrix[now][i] + distance[now];
      temp = matrix[now][i] + distance[now];
      if(temp < distance[i]){
    distance[i] = temp;
      }

      if(min > distance[i] && visited[i] == 0){
      min = distance[i]; count = i; route[i] = now;
      }
      }      
   

    }
    visited[count]++;  now=count; min = max;
    //count_t[j] = now;
  }
 
  /*
  printf("---------------------------------------\n"); 
  printf("４までの最短経路は\n");
  for(i = 0;i < N;i++){
    printf("%d>>",count_t[i]);
  }
  printf("終了\n");
  printf("---------------------------------------\n"); 
  */
}
//行列を表示する関数
void print_matrix(int a[][N])
{
  int i, j;
 
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++){
      printf("%8d ", a[i][j]);}
    printf("\n");
  }
  return;
}

試してたいこと

jを用いているループのなかで４回目以降で最短経路ではない場所に行ってしまいます。

そこの処理にかんしてアドバイスいただきたいです。
よろしくお願いします。

補足情報

Windows10
visualstdio

各頂点を訪れた際の処理に誤りがあるのではないかと思っています。

Comments

[takabosoft]

ダイクストラ法ちょっと調べてみたんですが、全部のノードを確定済みにしない限り最短経路は出ないアルゴリズムなのかと思います。「４回目以降で最短経路ではない場所に行ってしまいます」というのは、別に間違ってはいないのではないでしょうか？いっぱつで最短経路を当てるアルゴリズムではなさそうですが・・・。たぶん課題だと思いますが、その辺りは資料に書いてありませんか？

[windowsaa]

そこが異なることにより、最終的な最短経路の値も異なって出力されてしまいます。

[takabosoft]

「最終的な最短経路の値」を出すプログラムを載せてもらった方が良い気がします。
正解の値と合わせて。
また、各変数の意味、大まかなアルゴリズムの説明もあった方が良いと思います。
質問欄は編集できます。

[takabosoft]

少なくともダイクストラ法を調べてそこで載っていたアルゴリズムと、windowsaaさんが書いているコードはやり方が一致していないので、その不一致が問題点なのか、ただのアルゴリズムの微妙な方言なのか、が今の情報だけでは判断できません。もっと情報をください。

[izmktr]

プログラムを動かしてみましたが、distanceの値は全て正しいように見えます
例えば、0から1に行くとき、0→1より、0→3→1のほうが近いのですが、ちゃんと反映されています
具体的にどこへ行くときの値が間違っているのでしょうか

Answer 1

if(matrix[now][i] < max && visited[i] ==0 && matrix[now][i] > 0){
      // distance[i] = matrix[now][i] + distance[now];
      temp = matrix[now][i] + distance[now];
      if(temp < distance[i]){
          distance[i] = temp;
      }
}  //ここで閉じる
if(min > distance[i] && visited[i] == 0){
      min = distance[i]; count = i; route[i] = now;
}
//}  //削除  

ダイクストラ法走りませんが、距離で塗りつぶしていくやつかな、
多分、ifの中カッコの閉じる位置の間違いだと思います。