実現したいこと
それぞれの頂点からの最短経路をダイクストラ法により出力したい
発生しているエラー
エラーはありません
対象のソースコード
C
1#include<stdio.h> 2#define max 1000000 3#define N 7 4 5void print_matrix(int a[][N]); 6 7int main(void){ 8 9 int distance[N],visited[N],route[N],count_t[N]; 10 int i,j,k,count,min,now,temp; 11 12 int matrix[N][N] = { 13 { 0 , 17,max,max,max,max,max}, 14 { 17, 0 , 21, 7 ,max,max,max}, 15 {max, 21, 0 , 13, 5 ,max,max}, 16 {max, 7 , 13, 0 ,max, 5 ,max}, 17 {max,max, 5 ,max, 0 , 16, 22}, 18 {max,max,max, 5 , 16, 0 , 25}, 19 {max,max,max,max, 22, 25, 0 }}; 20 21 for(i=0;i<N;i++){ 22 visited[i] = 0; distance[i] = max; route[i] = -1 ; count_t[i] = 0; 23 } 24 25 print_matrix(matrix); 26 27 //初期化を行う 28 visited[0] = 1;distance[0] = 0; 29 now = j = k = 0; min = max; 30 31 for(j = 0;j < 5;j++){ 32 33 printf("---------------------------------------------------------------\n"); 34 printf("now = %d\n",now); 35 count_t[j] = now; 36 for(i=0;i<N;i++){ 37 printf(" %6d ",distance[i]); 38 } 39 40 printf("\n"); 41 42 for(i=0;i<N;i++){ 43 printf(" %6d ",visited[i]); 44 } 45 46 printf("\n"); 47 48 for(i=0;i<N;i++){ 49 printf(" %6d ",route[i]); 50 } 51 52 printf("\n"); 53 54 // visited[now] = 1; 55 for(i=0;i<N;i++){ 56 if(matrix[now][i] < max && visited[i] ==0 && matrix[now][i] > 0){ 57 // distance[i] = matrix[now][i] + distance[now]; 58 temp = matrix[now][i] + distance[now]; 59 if(temp < distance[i]){ 60 distance[i] = temp; 61 } 62 63 if(min > distance[i] && visited[i] == 0){ 64 min = distance[i]; count = i; route[i] = now; 65 } 66 } 67 68 69 } 70 visited[count]++; now=count; min = max; 71 //count_t[j] = now; 72 } 73 74 /* 75 printf("---------------------------------------\n"); 76 printf("4までの最短経路は\n"); 77 for(i = 0;i < N;i++){ 78 printf("%d>>",count_t[i]); 79 } 80 printf("終了\n"); 81 printf("---------------------------------------\n"); 82 */ 83} 84//行列を表示する関数 85void print_matrix(int a[][N]) 86{ 87 int i, j; 88 89 for(i=0;i<N;i++) { 90 for(j=0;j<N;j++){ 91 printf("%8d ", a[i][j]);} 92 printf("\n"); 93 } 94 return; 95}
試してたいこと
jを用いているループのなかで4回目以降で最短経路ではない場所に行ってしまいます。
そこの処理にかんしてアドバイスいただきたいです。
よろしくお願いします。
補足情報
Windows10
visualstdio
各頂点を訪れた際の処理に誤りがあるのではないかと思っています。
ダイクストラ法ちょっと調べてみたんですが、全部のノードを確定済みにしない限り最短経路は出ないアルゴリズムなのかと思います。「4回目以降で最短経路ではない場所に行ってしまいます」というのは、別に間違ってはいないのではないでしょうか?いっぱつで最短経路を当てるアルゴリズムではなさそうですが・・・。たぶん課題だと思いますが、その辺りは資料に書いてありませんか?
そこが異なることにより、最終的な最短経路の値も異なって出力されてしまいます。
「最終的な最短経路の値」を出すプログラムを載せてもらった方が良い気がします。
正解の値と合わせて。
また、各変数の意味、大まかなアルゴリズムの説明もあった方が良いと思います。
質問欄は編集できます。
少なくともダイクストラ法を調べてそこで載っていたアルゴリズムと、windowsaaさんが書いているコードはやり方が一致していないので、その不一致が問題点なのか、ただのアルゴリズムの微妙な方言なのか、が今の情報だけでは判断できません。もっと情報をください。
プログラムを動かしてみましたが、distanceの値は全て正しいように見えます
例えば、0から1に行くとき、0→1より、0→3→1のほうが近いのですが、ちゃんと反映されています
具体的にどこへ行くときの値が間違っているのでしょうか