p-メディアン問題のC言語プログラミング

Question

p-メディアン問題のプログラミングについて質問です。
例えばa.txtから以下のような数字を読み込んだ場合、

＜a.txt>

4//ノード数

2.0 0.5 1.0 3.0//重み
/*距離行列*/
0.0 4.0 5.0 7.0
4.0 0.0 3.0 3.0
5.0 3.0 0.0 4.0
7.0 3.0 4.0 0.0

行列を計算すると（実行すると）
0.000 8.000 10.000 14.000
2.000 0.000 1.500 1.500
5.000 3.000 0.000 4.000
21.000 9.000 12.000 0.000
合計
28.000 20.000 23.500 19.500

最初に重みと距離行列をかけて得られた数字に対して、１メディアンの場合、合計値の中の最小値が答えです。（今回は４列目）
２メディアンの場合は、その四列目は固定して,四列目と各列の値の値を比べ、小さい方の値を足していきます。そして、その中で最小値を取った列が選ばれます。
四列目と一列目の場合0+1.5+4+0=5.5
四列目と二列目の場合8+0+3+0=11
四列目と三列目の場合10+1.5+0+0=11.5
よって、２メディアンの値は１，４列目で5.5です。
このように計算するプログラムを作成したいのですが、どのように実装していいのか全くわかりませんでした。
とりあえず、1メディアン問題のプログラムは出来たので下に示します。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
const int FNLEN = 50;
const int MAX_N = 100;
int main()
{
  FILE *fp;
  int i, j, nnode;
  double dem[MAX_N], dist[MAX_N][MAX_N], wdist[MAX_N][MAX_N], wsum[MAX_N];
  char file_name[FNLEN];
  printf("Data file name: ");  scanf("%s", file_name);
  if ((fp = fopen(file_name,"r")) == NULL){
  printf("%s: ファイルをオープンできません!\n", file_name);
  return -1;
  }
  printf("データファイル名: %s\n", file_name);
  fscanf(fp,"%d",&nnode);
  if (nnode < 1 || nnode > MAX_N) {
  printf("ノードの数は1以上%3d以下にしてください！\n", MAX_N);
  return -1;
  }
  for (i = 0; i < nnode; i++){
    fscanf(fp, "%lf", &dem[i]);
  }
  for (i = 0; i < nnode; i++){
  for (j = 0; j < nnode; j++){
     fscanf(fp, "%lf", &dist[i][j]);
  }
  }fclose(fp);
  for (i = 0; i < nnode; i++) { // 行
   for (j = 0; j < nnode; j++) { // 列
     wdist[i][j] = dem[i] * dist[i][j];
       printf("%.3f ", wdist[i][j]);//出力
   }printf("\n");
  }puts("------------------\n合計");
   for (j = 0; j < nnode; j++) {
     wsum[j] = 0.0;
     for (i = 0; i < nnode; i++) {
       wsum[j] += wdist[i][j];
   }
    printf("%.3f ", wsum[j]);
  }
  int min_index = 0;
  for (j = 1; j < nnode; j++) {
     if (wsum[min_index] > wsum[j]) {
      min_index = j;
    }
  }
  printf("\n\n最小値の列番号は %dで、その合計は %.3f\n", min_index + 1, wsum[min_index]);
   return 0;
}

これをもとに実装したいのですが、どのようにすればいいのかがわからなかったので、もしわかる方がいらっしゃれば教えていただけるととても助かります。

Comments

[1T2R3M4]

https://qiita.com/YAT/questions/9da6122b99f5e3c1897d

以下ご対応ください。
https://teratail.com/help#posted-otherservice

Answer 1

ppaul氏の回答のコメント欄に書いた話

真の最適解は，「２店舗を同時に出店するとしたら，最適なのはどこか？」という話の解なんだけども，
それだと計算量の観点で解を探索するのが非常につらいので，妥協して
・まずは１店舗目を出店する．最適なのはどこか？
・「その後」，２店舗目を出店する．「２店舗目の」最適な場所はどこか
という形で考える，という話なのかな．
当然，この方法では「２店舗同時」の最適解は見つからず，局所解が得られる可能性がある，と．

について言えば…

まず，出店位置を探す際に，既に出店した場所を再度選んでしまわないように

• 各地点に店舗を出したかどうかを覚えておくフラグ F[]

的なのを用意して，

//出店する場所 k の決定
//F[場所]が「出店済」でない場所のなかから選ぶ．
for( 場所 )
{
  if( F[場所]==出店済 )continue;

  //行列のこの場所に対する列の合計が最小だったらkを更新
  if( /*略*/ ){ k = 場所; }
}
//（ここまでで k = 今回出店する場所 になっている）

//フラグ更新
F[ k ] = 出店済;

みたいな感じで出店場所を決定．
で，店舗を出店する場所が決定されたとき，

//出店場所 k が決定された後の行列の更新
for( 行列のすべての列について )
{
  //既に出店した列の要素は更新しなくてよい
  if( F[列]==出店済 )continue;

  //列の行列要素を更新
  for( この列のすべての行について )
  {//今回選ばれた列の値の方が小さければその値に更新する
    行列[行,列] = min( 行列[行,列], 行列[行,k] );
  }
}

みたくして，次回の出店場所決定処理時に計算される列の合計値が

２メディアンの場合は、その四列目は固定して,四列目と各列の値の値を比べ、小さい方の値を足していきます。

という話になるように行列を更新すればよいのではないでしょうか．

Answer 2

p-メディアン問題をちょっと調べて見ました。

ノードをA,B,C,D,Eとして

重みが
40.0 35.0 3.0 30.0 45.0

距離が
0.0 2.0 3.0 5.0 6.0
2.0 0.0 4.0 6.0 7.0
3.0 4.0 0.0 2.0 3.0
5.0 6.0 2.0 0.0 2.0
6.0 7.0 3.0 2.0 0.0

の場合を考えると、１メディアンであれば、最適解はCです。

それは積
499.0 587.0 455.0 506.0 554.0
をみれば分かります。

しかし、２メディアンであれば、最適解はAとEになりますね。
これはどうやって求めれば良いのかというアルゴリズムが分からないので、もう少し詳しく書いてもらえませんか。

---

YATさんが期待するのは以下のプログラムでよろしいですか。
関数分割をしたとき、本来であれば1次元配列に変えて受け渡しをするべきなのですが、そこまでやる気力がなく、外部変数とさせていただきました。変数名や関数名も間に合わせですみません。
また、k=1とk>2を同じアルゴリズムで書くために無限大を使っています。こういう使い方については賛否両論あるだろうとは思います。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define FNLEN  (50)
#define MAX_N (100)
#define NOTSELECTED (0)
#define SELECTED (1)

double dem[MAX_N]; //重み
double dist[MAX_N][MAX_N]; //距離
double wdist[MAX_N][MAX_N]; //重み付き距離
double wdistk[MAX_N][MAX_N]; //k番目の重み付き距離
double wsum[MAX_N]; //重み付き距離合計
double mindist[MAX_N]; //重みの最小値
int selected[MAX_N]; //既に選ばれた列
int nnode; // ノード数

void read_data(void) {
    FILE *fp;
    int i, j;
    char file_name[FNLEN];

    printf("Data file name: ");  scanf("%s", file_name);
    if ((fp = fopen(file_name,"r")) == NULL){
        printf("%s: ファイルをオープンできません!\n", file_name);
        exit(-1);
    }

    printf("データファイル名: %s\n", file_name);
    fscanf(fp,"%d",&nnode);
    if (nnode < 1 || nnode > MAX_N) {
        printf("ノードの数は1以上%3d以下にしてください！\n", MAX_N);
        exit(-1);
    }

    for (i = 0; i < nnode; i++){
        fscanf(fp, "%lf", &dem[i]);
    }
    for (i = 0; i < nnode; i++){
        for (j = 0; j < nnode; j++){
            fscanf(fp, "%lf", &dist[i][j]);
        }
    }
    fclose(fp);
    return;
}

void initialize(void) {
    int i;
    for (i=0; i<nnode; i++) {
        mindist[i] = INFINITY;
        selected[i] = NOTSELECTED;
    }
}

void cal_wdist(void) {
    int i, j;

    for (i = 0; i < nnode; i++) {
        for (j = 0; j < nnode; j++) {
            wdist[i][j] = dem[i] * dist[i][j];
        }
    }
    return;
}

void print_double(double d) {
    if (d == INFINITY) {
        printf("  -   ");
    }
    else {
        printf("%5.1f ", d);
    }
}

void print_wdistk(int k, int select) {
    int i, j;

    printf("     ");
    for (i=0; i < nnode; i++) {
        printf(" N%03d ", i+1);
    }
    printf("\n");

    for (i = 0; i < nnode; i++) {
        printf("N%03d ", i+1);
        for (j = 0; j < nnode; j++) {
            print_double(wdistk[i][j]);
        }
        printf("\n");
    }
    printf("合計 ");
    for (j = 0; j < nnode; j++) {
        print_double(wsum[j]);
    }
    printf("\n\nk=%dの最小値の列番号は %dで、その合計は ", k, select + 1);
    print_double(wsum[select]);
    printf("\n\n\n");
    return;
}

int cal_wdistk(void) {
    int i, j;
    int min_index = 0;

    for (j = 0; j < nnode; j++) {
        for (i = 0; i < nnode; i++) {
            if (selected[j] == SELECTED) {
                wdistk[i][j] = INFINITY;
            }
            else if (wdist[i][j] < mindist[i]) {
                wdistk[i][j] = wdist[i][j];
            }
            else {
                wdistk[i][j] = mindist[i];
            }
        }
    }
    for (j = 0; j < nnode; j++) {
        wsum[j] = 0.0;
        for (i = 0; i < nnode; i++) {
            wsum[j] += wdistk[i][j];
        }
    }
    for (j = 1; j < nnode; j++) {
        if (wsum[min_index] > wsum[j]) {
            min_index = j;
        }
    }
    return min_index;
}

void update(int select) {
    int j;

    selected[select] = SELECTED;
    for (j=0; j < nnode; j++) {
        if (wdist[j][select] < mindist[j]) {
            mindist[j] = wdist[j][select];
        }
    }
}

int main()
{
    int k, select;

    read_data();
    initialize();
    cal_wdist();

    for (k=1; k < nnode; k++) {
        select = cal_wdistk();
        print_wdistk(k, select);
        update(select);
    }

    return 0;
}

出力例は以下です。

データファイル名: b.txt
      N001  N002  N003  N004  N005
N001   0.0  80.0 120.0 200.0 240.0
N002  70.0   0.0 140.0 210.0 245.0
N003   9.0  12.0   0.0   6.0   9.0
N004 150.0 180.0  60.0   0.0  60.0
N005 270.0 315.0 135.0  90.0   0.0
合計 499.0 587.0 455.0 506.0 554.0

k=1の最小値の列番号は 3で、その合計は 455.0


      N001  N002  N003  N004  N005
N001   0.0  80.0   -   120.0 120.0
N002  70.0   0.0   -   140.0 140.0
N003   0.0   0.0   -     0.0   0.0
N004  60.0  60.0   -     0.0  60.0
N005 135.0 135.0   -    90.0   0.0
合計 265.0 275.0   -   350.0 320.0

k=2の最小値の列番号は 1で、その合計は 265.0


      N001  N002  N003  N004  N005
N001   -     0.0   -     0.0   0.0
N002   -     0.0   -    70.0  70.0
N003   -     0.0   -     0.0   0.0
N004   -    60.0   -     0.0  60.0
N005   -   135.0   -    90.0   0.0
合計   -   195.0   -   160.0 130.0

k=3の最小値の列番号は 5で、その合計は 130.0


      N001  N002  N003  N004  N005
N001   -     0.0   -     0.0   -
N002   -     0.0   -    70.0   -
N003   -     0.0   -     0.0   -
N004   -    60.0   -     0.0   -
N005   -     0.0   -     0.0   -
合計   -    60.0   -    70.0   -

k=4の最小値の列番号は 2で、その合計は  60.0

Comments

[YAT]

回答ありがとうございます。
回答者様の数値を参考に答えさせていただきます。
1メディアン(上記のプログラム)を実行した結果、答えは以下のようになりました。
（A B C D E)
0 80 120 200 240
70 0 140 210 245
9 12 0 6 9
150 180 60 0 60
270 315 135 90 0
________________
合計
499 587 455 506 554
最小値の列番号は3で、その合計は455

1-メディアンであれば、最適解は積の最小値であるCが選ばれます。

ここで、p-メディアン(p≧2)の話をさせていただきます。
①p=2の時、
1メディアンで選ばれた最適値のCはそのまま生かし、Cを中心に各列の要素と比較していきます。(なお、各列の要素と比較する際は二つの値のうち最小である方の値を足していきます。)
（i)AとCを比較
列Aと列Cは上記にも示した通り
A C
0 120 (最小は0)
70 140 (最小は70)
9 0 (最小は0)
150 60 (最小は60)
270 135 (最小は135)
より、この二つのうち最小の値を足していくので
0+70+0+60+135=265
(ii)BとCを比較
B C
80 120　（最小は80）
0 140　（最小は0）
12 0　　（最小は0）
180 60　　（最小は60）
315 135　（最小は135）
よって同様に80+0+0+60+135=275
(iii)CとDを比較
C　　D
120 200(最小は120)
140 210(最小は140)
0 6 (最小は0)
60 0 (最小は0)
135 90 (最小は90)
よって、120+140+0+0+90=350
(iv)CとEを比較
C E
120 240(最小は120)
140 245(最小は140)
0 9 (最小は0)
60 60 (最小は60)
135 0 (最小は0)
よって、120+140+0+0+60=320

このことから、(i)～(iv)の結果の中で、一番小さい値を取ったのは、AとCの265より　p=2のとき、最適値はAとCの265となります。

②p=3のとき
p=2のとき、AとCが選ばれたので、AとCは固定してそれらを元に
各列について考える。
(i)A,CとBを比較
A B C
0 80 120(最小は0)
70 0 140(最小は0)
9 12 0 (最小は0)
150 180 60 (最小は60)
270 315 135(最小は135)
よって、0+0+0+60+135=195
(ii)A,CとDを比較
A C D
0 120 200(最小は０)
70 140 210(最小は70)
9 0 6 (最小は0)
150 60 0 (最小は0)
270 135 90 (最小は90)
よって、0+70+0+0+90=160
(iii)A,CとEを比較
A C E
0 120 240（最小は0）
70 140 245(最小は70)
9 0 9　（最小は0）
150 60 60　（最小は60）
270 135 0　　（最小は0）
よって、0+70+0+60+0=130

これらのことより、(i)～(iii)のなかで最小値を取ったのは、130より
p=3のとき、最適値はA,C,Eで130となる。

③p=4のとき
p=3のとき、A,C,Eが選ばれたので、それらを固定して各列について考える。
(i)A,C,EとBを比較する
A B C E
0 80 120 240(最小は0)
70 0 140 245（最小は0）
9 12 0 9　　(最小は0）
150 180 60 60　(最小は60）
270 315 135 0 　(最小は0）
よって、60
(ii)A,C,EとDを比較する
A C D　 E
0 120 200 240(最小は0)
70 140 210 245（最小は70）
9 0 6 9　　(最小は0）
150 60 0 60　(最小は0）
270 135 90 0 　(最小は0）
よって、70
(i).(ii)の中で最小値を取ったのは(i)より最適値はA,B,C,Eで60

④p=5のとき
最小値はすべて0より　最適値はA,B,C,D,E で0となる

pメディアン法は
このように、最初(p=1)では、各列の和の最小値を取る列が選ばれ、
それ以降は、前の操作で選ばれた列を中心に、各列の要素と比べ、
その中で最小を取る値を足していく。
その上で、和の一番最小を取った列が、前の操作で選ばれた列に加え追加されるというものです。

もしまだわかりにくい箇所がありましたら、教えてくれるととても助かります。

[ppaul]

pメディアン法は昨日、以下の内容を読んだだけなので私が間違っているかもしれません。

https://www.msi.co.jp/nuopt/docs/v19/examples/html/02-10-00.html

昨日の例は以下のように考えました。
A市の人口が40,000人、
B市の人口が35,000人、
C市の人口が 3,000人、
D市の人口が30,000人、
E市の人口が45,000人、
A市とB市の間の道路は2km
A市とC市の間の道路は3km
B市とC市の間の道路は4km
C市とD市の間の道路は2km
C市とE市の間の道路は3km
D市とE市の間の道路は2km
他の道路はない

このとき、p個の店を出店するとき、どの町に店を出せば良いか。
住民×移動距離の合計が最小になるようにせよ。

店を一個出すのだと、C市は人口は少ないけれども他の市と全て道路があるのでここに建てるのが一番いいですね。
A市の人の移動　40千人×3km　　120
B市の人の移動　35千人×4km　　140
C市の人の移動　 3千人×0km　　 0
D市の人の移動　30千人×2km　　 60
E市の人の移動　45千人×3km　　135
　　　　　　　　　　　合計　　455
店を二個出すのだと、人口の多いA市とE市に出せば、あまり人が移動しないので一番良さそう。
A市の人の移動　40千人×0km　　 0
B市の人の移動　35千人×2km　　 70
C市の人の移動　 3千人×3km　　 9
D市の人の移動　30千人×2km　　 60
E市の人の移動　45千人×0km　　 0
　　　　　　　　　　　合計　　139

なぜ、A市とC市の265が答えになるのかが良くわかりません。

[YAT]

回答ありがとうございます。
確かに私も最初はそのように思いました。

先日用いた行列を以下に示します。（少し見にくい箇所を含みすみません。）
(A　　B　　　C　　　D　　　　E)
0　　80　　120　　200　　240
70　 　0　　140　　210　　245
9　　12　 　 0　　　 6　　　 9
150　180　　60　　　0　　　60
270　315　　135　　90　　　0

例えばp=2のとき、
私も最初は、上記行列の中で最小値を取るのはA,Eの139だと思いました。

ですが、その場合すべての場合を調べる必要があり、その場合の数は
5C2=10通りであります。
それは列数が5個程度のものならばなんとか力ずくで探すことはできますが、列数が100個ともなるとかなり困難であり、そのためにp=2ではp=1で用いた最適解を中心に計算していくのです。

そうすると、上記の行列の場合Cを中心に4通りで済みます。

それゆえ、Cを中心に考えると、
①A,Cでは　0+70+0+60+135=265
②B,Cでは　80+0+0+60+135=275
③C,Dでは　120+140+0+0+90=350
④C,Eでは　120+140+0+60+0=320
よって、p=2の時の最適値は、A,Cの265となります。

私も、pメディアン法がなぜこのようなことをするのかはよくわかりませんが、
私はpメディアン法とはそのようなものと聞きました。

また、もし不明な点があればお尋ねください。

[fana]

真の最適解は，「２店舗を同時に出店するとしたら，最適なのはどこか？」という話の解なんだけども，
それだと計算量の観点で解を探索するのが非常につらいので，妥協して

・まずは１店舗目を出店する．最適なのはどこか？
・「その後」，２店舗目を出店する．「２店舗目の」最適な場所はどこか

という形で考える，という話なのかな．
当然，この方法では「２店舗同時」の最適解は見つからず，局所解が得られる可能性がある，と．

[YAT]

その認識で正しいです。

[YAT]

ところで、pメディアンのプログラムの質問についてはどうなっているのでしょうか。
恐縮ですが、ヒントでもいいので頂けると、とても助かります。

[ppaul]

今、コーディングしていますので、しばらくお待ちいただけますか。
私が理解できるように関数の分割とかインデントとかを変更していますが、それはご了承ください。

[YAT]

回答ありがとうございます。とても助かりました。
より理解を深めるため、じっくり考えてプログラムのコメントも記載しようと考えています。
また、コメントの意味が正しいかどうかで見てもらうときがあれば、その時はよろしくお願いします。

[YAT]

p-メディアン問題のC言語プログラミングについて、
（少し書き換えました）
一様以下のようなコメントを付けました。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define FNLEN (50)/* ファイル名の長さ */
#define MAX_N (100)/* ノード数最大値 */

double dem[MAX_N]; //重み
double dist[MAX_N][MAX_N]; //距離
double wdist[MAX_N][MAX_N]; //重み付き距離
double wdistk[MAX_N][MAX_N]; //k番目の重み付き距離
double wsum[MAX_N]; //重み付き距離合計
double mindist[MAX_N]; //重みの最小値
int selected[MAX_N]; //既に選ばれた列
int nnode; // ノード数

void print_double(double d)
{
if (d == INFINITY) {
printf(" - ");
}
else {
printf("%5.1f ", d);//出力
}
}

int cal_wdistk(void) //一つの数字を記憶する関数（最小値を取る列を返す関数）
{
int i, j;
int min_index = 0;//初期化

for (j = 0; j < nnode; j++) {
for (i = 0; i < nnode; i++) {
if (selected[j] == 1) {
wdistk[i][j] = INFINITY;//すでに選ばれた列は削除
}
else if (wdist[i][j] < mindist[i]) {
wdistk[i][j] = wdist[i][j];
}
else {
wdistk[i][j] = mindist[i];
}
}
}
for (j = 0; j < nnode; j++) {
wsum[j] = 0.0;
for (i = 0; i < nnode; i++) {//各列の和を計算
wsum[j] += wdistk[i][j];
}
}
for (j = 1; j < nnode; j++) {
if (wsum[min_index] > wsum[j]) {//和の最小を取る行を探索
min_index = j;
}
}
return min_index;//最小値を取る列を返す

}

void print_wdistk(int k, int select) //kを配置する施設の数としたとき、p=n(1≦p≦k)での最適値を求める関数
{
int i, j;

printf(" ");
for (i=0; i < nnode; i++) {
printf(" N%03d ", i+1);
}
printf("\n");

for (i = 0; i < nnode; i++) {
printf("N%03d ", i+1);
for (j = 0; j < nnode; j++) {
print_double(wdistk[i][j]);
}
printf("\n");
}
printf("合計 ");
for (j = 0; j < nnode; j++) {
print_double(wsum[j]);//p=n(n≦k)の各列の和
}

printf("\n\np=%dのとき追加される一つの施設は %dで、その合計は ", k, select + 1);
print_double(wsum[select]);//選ばれた列の合計を出力
printf("\n\n\n");

}

void update(int select)
{
int j;

selected[select] = 1;//すでに選ばれた列は削除する
for (j=0; j < nnode; j++) {
if (wdist[j][select] < mindist[j]) {
mindist[j] = wdist[j][select];
}
}
}

int main()
{

FILE *fp;
int i, j;
char file_name[FNLEN]; /* データファイル名 */

printf("Data file name: "); scanf("%s", file_name);
if ((fp = fopen(file_name,"r")) == NULL){/* ファイルオープンに失敗した場合は終了 */
printf("%s: ファイルをオープンできません!\n", file_name);
exit(-1);
}

printf("データファイル名: %s\n", file_name);
fscanf(fp,"%d",&nnode);/* ノード数の読み込み */
if (nnode < 1 || nnode > MAX_N) {
printf("ノードの数は1以上%3d以下にしてください！\n", MAX_N);
exit(-1);
}

printf("重み\n");
for (i = 0; i < nnode; i++){
fscanf(fp, "%lf", &dem[i]);/*重み行列の読み込み*/
printf("%5.1f ",dem[i]);
}printf("\n\n");

for (i = 0; i < nnode; i++){
for (j = 0; j < nnode; j++){
fscanf(fp, "%lf", &dist[i][j]);/* 距離行列の読み込み */

}
}
for (i=0; i<nnode; i++) {
mindist[i] = INFINITY;
selected[i] = 0;
}
fclose(fp); /* ファイルクローズ */
/* 重み付き距離行列の計算(p-median) */
printf("重み付き距離行列\n");
for (i = 0; i < nnode; i++) {
for (j = 0; j < nnode; j++) {
wdist[i][j] = dem[i] * dist[i][j];
printf("%5.1f ",wdist[i][j]);//出力
}printf("\n");
}
printf("合計___________________________\n");
for (j = 0; j < nnode; j++) {//各列の和を計算
wsum[j] = 0.0;
for (i = 0; i < nnode; i++) {
wsum[j] += wdist[i][j];
}
printf("%5.1f ", wsum[j]);//出力
}printf("\n\n");
/* ---- 貪欲算法 start ---- */
int k, select;

int a;
printf("配置する施設の数を入力してして下さい p= "); scanf("%d",&a);

for(k=1;k<=a;k++){
select = cal_wdistk();
print_wdistk(k, select);
update(select);
}

/* ---- 貪欲算法 end ---- */
return 0;
}

ただ、一つ分からなかったのは、関数「 cal_wdistk」の
else if (wdist[i][j] < mindist[i]) {
wdistk[i][j] = wdist[i][j];
}
else {
wdistk[i][j] = mindist[i];
}

の部分が何を意味しているのかがよくわからなかったので、教えてくれるととても助かります。
また、以上のコメントアウトで正しいでしょうか。
よろしくお願いします。

[ppaul]

mindistというのは、重みの最小値と書いておきましたが、もっと正確に言うと、各町から既に選ばれた町のどれかへの重みの最小値です。

質問のif else if elseは、
その町が既に選ばれているなら、最小値を取るときには除外するように無限大を入れておく。
まだ選ばれていないなら、wdistk[i][j] = min(wdist[i][j], mindist[i])　つまり、小さい方の距離を入れておく、です。本当はMINというマクロでも作った方が読みやすかったのでしょうが、そこは手抜きです。

その他のレビュー依頼は以下の理由でお断りします。
私は読み込み部分、初期化部分、選択部分、更新部分を分けて書いておきました。
職業プログラマーの場合、プログラムを機能別に分割するのは構成設計と呼び、非常に重要な技術です。
バグを早期に検出可能とし、保守性や再利用姓を向上するためには、適切な分割、適切な関数名や適切な変数名は、コメントを付ける以上に重要です。(今回は手抜きなので関数名や変数名は変更しませんでした)

もしも、プログラムをどのような理由で分割したのかという質問であれば、良いプログラマーを育成するために、いろいろと説明したことでしょう。
しかし、なぜ分割したのかを理解できない人のために時間をかけるよりは、本当に困っている人や、将来育ちそうな人のために時間をかける方が優先順位が高いと思うのです。

プログラムを改変するのは個人の自由です。私は口を出しません。しかし、改変したプログラムの責任は自身にあることを理解してください。