プリム法の出力結果が模範解答と異なるので困っています。

Question

プリム法について勉強について勉強しているのですが入力が100×100隣接行列の時に結果が少しだけ異なってしまいます。
問題としては最小全域木で与えられた重み付きグラフに対する最小全域木の辺の重みの総和を計算するプログラムを作成すると言うものです。
Prims関数に関して何かおかしなところがあれば教えていただきたいです。
問題はこちらです。
問題
うまくいかない入力例はこちらです。
入力例

本来なら出力結果が
3864
となるはずなのですが
3991
となってしまいます。

#include<stdio.h>
#define max 1000
#define inf 100000

int vertex_num,admat[max][max];

int Prims(){
  int i,j,u,v,cost[max][max],min_distance;
  int visit[max],no_edges,min_cost,distance[max],from[max];
  
  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
      if(admat[i][j]==0){
          cost[i][j]=inf;
      }else{
          cost[i][j]=admat[i][j];
      }
    }
  }
  distance[0]=0;
  visit[0]=1;

  for(i=1;i<vertex_num;i++){
      distance[i]=cost[0][i];
      from[i]=0;
      visit[i]=0;
  }
  min_cost=0;
  no_edges=vertex_num-1;

  while(no_edges>0){
     min_distance=inf;
     for(i=1;i<vertex_num;i++){
         if(visit[i]==0 && distance[i]<min_distance){
             v=i;
             min_distance=distance[i];
         }
     }
     u=from[v];
     no_edges--;
     visit[v]=1;
     for(i=1;i<vertex_num;i++){
         if(visit[i]==0 && cost[i][v]<distance[i]){
             distance[i]=cost[i][v];
             from[i]=v;
         }
     }
     min_cost+=cost[u][v];
  }
  
  return min_cost;
}

int main(){
  //admatは隣接行列
  int i,j;

  scanf("%d",&vertex_num);
  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
      scanf("%d",&admat[i][j]);
    }
  }
  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
       if(admat[i][j]==-1){
           admat[i][j]=0;
       }
       //printf("%d ",admat[i][j]);
    }
  }
  
  printf("%d\n",Prims());
  return 0;
}

Answer 1

回答ではないですが、

C言語のコードを組みたいのであれば、デバッグ環境を整えましょう
WindowsであればVisualStudio、そうでなければEclipseなど、
これらの統合環境では、C言語のコードの任意の行で実行を停止させ、変数の値を参照したり、１行づつステップ実行させて変数の値を追いかけるなどができるようになります
そうすれば、あてずっぽでコードを組む、ということをしなくて済みます

Comments

[Teemro_431265]

あてずっぽでコードは組んでません。

[y_waiwai]

ソースデバッグできる環境をお持ちなら、どこで計算がおかしくなっていっているのか、というのを探っていきましょう。
すでにそういうことはやってる、というのであれば、この回答は無視してください。

＃で、できればどこでおかしいのかというのを追記していただけるとありがたいです

[pepperleaf]

これ、ちょっと追ってみたけど、単純にデバッグ環境があるからと言ってデバッグできるとは思えない。
プリム法に関する知識が無いと厳しそう。コードそのものは、デバッガなんか無しでも追跡は容易。ただし、意味するところが、、。ちょっと調べてみたが、まだ理解できず。
あ、Visual Studio 2017 の cl でコンパイルしたら、実行時にエラー無し終了。どうもstackサイズオーバーか? ローカルをグローバルに移して実行できました。

Answer 2

  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
       if(admat[i][j]==-1){
           admat[i][j]=0;
       }
       //printf("%d ",admat[i][j]);
    }
  }

が間違いでは?

参照ページの制約条件に

0≤aij≤2,000 (aij≠−1 のとき)

があります。
上記箇所を削除すると共に、

      if(admat[i][j]==0){
          cost[i][j]=inf;

を

      if(admat[i][j]==-1){
          cost[i][j]=inf;

とする。

手元の計算では、 3864 となりました。
(実際にうまくいかない入力例には、0が含まれています)

[追記]
結局、プリム法は理解できないまま。

Comments

[Teemro_431265]

回答ありがとうございます。
まだ何が悪いのかはわかっていないので参考にさせていただきます。