ここにあなたのための完全な解決策があります。固定配列を使用するという@ptsの提案と、ネストされたループのペアで明示的に配列を初期化するというコメントからの提案を使用しました。また、アルゴリズムの動作方法を自由に変更できます。たとえば、有向グラフまたは無向グラフのいずれかを使用するオプションを使用して、デバッグに役立つ中間出力を含める方法を示します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM
#define NMAX 20
int n;
void shortestPath(int m[NMAX][NMAX]);
void printMatrix(int m[NMAX][NMAX]);
// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"
int main(void) {
int i, j, weight, ret;
// open input file:
FILE *fp = fopen("eg2.txt", "r");
if(fp == NULL) {
printf("cannot read input file\n");
exit(1);
}
// read number of nodes in the graph:
fscanf(fp, "%d", &n);
if(n > NMAX) {
printf("input too large\n");
fclose(fp);
exit(1);
}
printf("n is %d\n", n);
// generate matrix:
int matrix[NMAX][NMAX];
for(i=0; i<NMAX;i++)
for(j=0; j<NMAX; j++)
matrix[i][j] = INF;
while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
if(ret == 3) {
matrix[i][j] = weight;
#ifdef SYM
matrix[j][i] = weight;
#endif
}
else printf("error reading input\n");
}
fclose(fp);
printMatrix(matrix);
shortestPath(matrix);
printMatrix(matrix);
}
void printMatrix(int m[NMAX][NMAX]) {
int i, j;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(m[i][j]==INF) printf(" - "); else printf("%3d ", m[i][j]);
}
printf("\n");
}
}
void shortestPath(int d[NMAX][NMAX]) {
int i, j, k, temp;
// no need to make a copy of the matrix: operate on the original
for(k=0; k<n; k++) {
for(i=0; i<n-1; i++) {
for(j=0; j<n; j++) {
if(i==j) continue; // don't look for a path to yourself...
if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
if((temp = d[i][k] + d[k][j]) < d[i][j]) {
d[i][j] = temp;
#ifdef SYM
d[j][i] = temp;
#endif
printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
}
}
}
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
}
}
}
次の入力ファイルを使用します。
5
1 2 3
2 4 2
1 4 8
0 3 7
3 1 2
1 4 2
1 3 1
0 1 1
私は出力として得ました：
n is 5
- 1 - 7 -
- - 3 1 2
- - - - 2
- 2 - - -
- - - - -
from 0 to 2 is shorter via 1: 1 + 3 is 4
from 0 to 3 is shorter via 1: 1 + 1 is 2
from 0 to 4 is shorter via 1: 1 + 2 is 3
from 3 to 2 is shorter via 1: 2 + 3 is 5
from 3 to 4 is shorter via 1: 2 + 2 is 4
0 1 1
0 2 4
0 3 2
0 4 3
1 2 3
1 3 1
1 4 2
2 4 2
3 1 2
3 2 5
3 4 4
- 1 4 2 3
- - 3 1 2
- - - - 2
- 2 5 - 4
- - - - -
奇妙なことに、コードを実行すると (上記のように)、同じ解決策が得られましたが、最初の部分の出力では、memset期待どおりに機能していないことが非常に明確でした:
0 1 252645135 7 252645135
252645135 0 3 1 2
252645135 252645135 0 252645135 2
252645135 2 252645135 0 252645135
252645135 252645135 252645135 252645135 0
0 1 1
0 2 4
0 3 2
0 4 3
1 2 3
1 3 1
1 4 2
2 4 2
3 1 2
3 2 5
3 4 4
memset実際、演算で行列に書き込まれている数値0x0F0F0F0Fは252645135で、10 進数です。なぜそうなのかは、次の構文をmemset見れば理解できます。
void *memset(void *str, int c, size_t n)
パラメータ
str --これは、埋めるメモリのブロックへのポインタです。
c --設定する値です。unsigned char値は int として渡されますが、関数はこの値の変換を使用してメモリ ブロックを埋めます。
n --これは、値に設定されるバイト数です。
16 進表現の 9999 と組み合わせると、
0x270F
intの「unsigned char変換」は、256 を法とするその数値、または最下位バイトです。この場合、最下位バイトは0x0Fブロック内のすべてのバイトに (繰り返し) 書き込まれる値です。したがって、値0x0F0F0F0F(私のマシンでは、anintは 4 バイト長) です。
あとがき
最後に、「任意のサイズの配列」を使用する場合は、次の関数をプログラムに追加し、示されているように関数シグネチャを置き換えることができます。これは、C で可変サイズの 2 D 配列を作成する「トリッキーな」方法です。基本的に、C が型のポインターに遭遇すると、int**2 回逆参照します。このポインターからポインターへのポインターがメモリーのブロックへのポインターのブロックを指すようにすることで、実質的に、コンパイラーが理解できる 2D 配列を作成します。
int **make2D(int r, int c) {
int ii, **M;
M = malloc(r * sizeof(int*) );
M[0] = malloc( r * c * sizeof(int) );
for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
return M;
}
void free2D(int** M) {
free(M[0]);
free(M);
}
次に、マトリックスを生成します
int **matrix;
matrix = make2D(n, n);
関数シグネチャを次のように変更します。
void shortestPath(int **m);
void printMatrix(int **m);
そして、それらを呼び出す
shortestPath(matrix); // etc
すべてが適切に機能するようにするには、コードで他のいくつかの調整を行う必要があります (例: 割り当てたメモリよりも少ないメモリを割り当てた場合、NMAX by NMAX 配列のすべての要素に INF を割り当てようとしないでください)。自分でこれを理解しようとすることもできますが、念のため、ここに完全なコードを示します。私が行ったもう 1 つの変更 -nグローバル変数として削除し、それをローカルにしましたmain(そして、それを必要とするさまざまなルーチンに渡しました)。これは通常、良い方法です。グローバルと混同しやすいため、どうしても選択の余地がない場合にのみ使用してください。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM
void shortestPath(int **m, int n);
void printMatrix(int **m, int n);
// create 2D matrix of arbitrary (variable) size
// using standard C:
int **make2D(int r, int c) {
int ii, **M;
M = malloc(r * sizeof(int*) );
M[0] = malloc( r * c * sizeof(int) );
for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
return M;
}
void free2D(int** M) {
free(M[0]);
free(M);
}
// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"
int main(void) {
int i, j, n, weight, ret;
// open input file:
FILE *fp = fopen("eg2.txt", "r");
if(fp == NULL) {
printf("cannot read input file\n");
exit(1);
}
// read number of nodes in the graph:
fscanf(fp, "%d", &n);
printf("n is %d\n", n);
// generate matrix:
int **matrix;
// allocate memory:
matrix = make2D(n, n);
// fill all elements with INF:
for(i=0; i<n;i++)
for(j=0; j<n; j++)
matrix[i][j] = INF;
// read the input file:
while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
if(ret == 3) {
matrix[i][j] = weight;
#ifdef SYM
// if undirected edges, put in both paths:
matrix[j][i] = weight;
#endif
}
else printf("error reading input\n");
}
fclose(fp);
printMatrix(matrix, n);
shortestPath(matrix, n);
printMatrix(matrix, n);
}
void printMatrix(int **m, int n) {
int i, j;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(m[i][j]==INF) printf(" - "); else printf("%3d ", m[i][j]);
}
printf("\n");
}
}
void shortestPath(int **d, int n) {
int i, j, k, temp;
// no need to make a copy of the matrix: operate on the original
for(k=0; k<n; k++) {
for(i=0; i<n-1; i++) {
for(j=0; j<n; j++) {
if(i==j) continue; // don't look for a path to yourself...
if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
if((temp = d[i][k] + d[k][j]) < d[i][j]) {
d[i][j] = temp;
#ifdef SYM
d[j][i] = temp;
#endif
printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
}
}
}
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
}
}
}
