c言語でのダイクストラ法の実装
大学の課題で、c言語におけるダイクストラ法について以下のようなものが出たのですが出力のためにどのようなコードを書けばいいかわかりません。どなたかコードや実装方法を教えていただけないでしょうか。
（入力例）
7
-1 7 3 6 -1 -1 4
7 -1 5 -1 6 -1 -1
3 5 -1 4 1 3 5
6 -1 4 -1 -1 -1 7
-1 6 1 -1 -1 2 -1
-1 -1 3 -1 2 -1 9
4 -1 5 7 -1 9 -1
1
１行目は頂点の数、２行目以降の各行は隣接行列の各要素を空白区切りで表し、最後の行の数はスタートの頂点の番号
[出力]
1. スタートとして選択した頂点から各頂点への最短経路とコストを以下の形式で
出力する．ここで s はスタートの頂点， g はゴールの頂点， c は合計のコス
トを表す．また s ... g は最短経路の各頂点を空白区切りとして表す．
s-->g : c ( s ... g )
以下は上記の入力例の場合の出力例
Input>1 <-- スタートとして選択した頂点番号
1-->0 : 7 ( 1 0 )
1-->1 : 0 ( 1 )
1-->2 : 5 ( 1 2 )
1-->3 : 9 ( 1 2 3 )
1-->4 : 6 ( 1 4 )
1-->5 : 8 ( 1 2 5 )
1-->6 : 10 ( 1 2 6 )
↓自分の書いたコード
#include <stdio.h>#include <limits.h>#define FALSE 0
#define TRUE (!FALSE)
#define INFINITY INT_MAX
#define MAXSIZE 100
int dijkstr(int number_of_vertex, int weight[][MAXSIZE], int start_vertex){
int is_in_mst[MAXSIZE], d[MAXSIZE];
int i, j, number_of_edges, min_d, v;
printf("Input>%d\n", start_vertex);
for (i = 0; i <number_of_vertex; i++) is_in_mst[i] = FALSE;
for (i = 0; i <number_of_vertex; i++) d[i] = INFINITY;
d[start_vertex] = 0;
for(number_of_edges = 0; number_of_edges<(number_of_vertex-1); number_of_edges++) {
min_d = INFINITY;
v = INFINITY;
for (i = 0; i <number_of_vertex; i++) {
if(is_in_mst[i] == FALSE &&d[i] <min_d) {
min_d = d[i]; v = i;}}
if(v != INFINITY)
is_in_mst[v] = TRUE;
for (i = 0; i <number_of_vertex; i++) {
if(is_in_mst[i] == FALSE &&weight[i][v] != INFINITY &&(weight[i][v] + d[v]) <d[i])
d[i] = weight[i][v] + d[v];}}}
int main(void){
int weight[MAXSIZE][MAXSIZE];
int i, j, data, n, start;
printf("Input data size>");
scanf("%d", &n);
printf("%d\n", n);
for (i = 0; i <n; i++) {
for(j = 0; j <n; j++) {
printf("Input data>");
scanf("%d", &data);
printf("%d\n", data);
weight[j][i] = data;
if(weight[j][i] == -1) weight[j][i] = INFINITY;}}
printf("\n");
printf("Input start vertex>");
scanf("%d", &start);
return 0;}
お礼
有難うございます。 デモも分かりやすかったです。