|
ダイクストラのアルゴリズムを使って、最短パスを探すプログラムを作りましたが、うまく動くことができません。
どのようにすれば、うまく動くことができるのでしょうか。どうか、よろしくお願いします。
#include <stdio.h>
#include <stdlib.h>
/* 最大ノード数 */
#define MAX_NODES 64
#define MAX_EDGES 2016
/* ノードのデータ構造 */
struct node
{
char label; /* ラベル */
struct node_list *nd_list; /* 接続するリスト
*/
};
/* 枝のデータ構造 */
struct edge
{
int nd1_idx, nd2_idx;
int weight; /* 枝重み */
};
/* リスト表現によるグラフの枝構造 */
struct node_list
{
int nd_idx; /* ノード番号 */
int eg_idx; /* 枝番号 */
struct node_list *next; /* 次のポインタ */
};
/* ノード数 */
static int node_n;
/* 枝数 */
static int edge_n;
/* ノードの配列 */
static struct node node[MAX_NODES];
/* 枝の配列 */
static struct edge edge[MAX_EDGES];
/*最短パスの重み*/
int wgoukei;
/* プロトタイプ宣言 */
int input_graph(char * );
int add_node_list(struct node * , int , int );
int dai_search(char ,char);
/*
* メインプログラム
*/
int
main(
int argc, /* 引数の数 */
char **argv /* 引数 */
)
{
/*
実行例:
% a.out file a f
*/
if(argc < 4){
printf("正しく情報が入力されていません\n");
exit(1);
}
/* グラフ情報をファイルから入力 */
input_graph(argv[1]);
/*ダイクストラで最短パスを検索*/
dai_search(argv[2][0], argv[3][0]);
/* 終了 */
return 0;
}
/*グラフの入力*/
int input_graph(char *fname)
{
FILE *fp;
int i,j,k;
char n1,n2;
int w;
/*入力ファイルオープン*/
if((fp=fopen(fname,"r"))==NULL)
{
printf("ファイルを開く際にエラーが発生しました\
n");
exit(1);
}
/*ノード情報の読み込み*/
fscanf(fp,"N=%d\n",&node_n);
for(i=0;i<node_n;i++)
{
fscanf(fp,"%c\n",&n1);
/*ラベルのセット*/
node[i].label =n1;
/*リストの初期化*/
node[i].nd_list = NULL;
}
/*枝情報の読み込み*/
fscanf(fp,"E=%d\n",&edge_n);
for(i=0;i<edge_n;i++)
{
/*ノード１ラベル、ノード２ラベル 枝の重み*/
fscanf(fp,"%c %c %d",&n1,&n2,&w);
for(j=0;j<node_n;j++)
if(n1==node[j].label) break;
for(k=0;k<node_n;k++)
if(n2==node[k].label) break;
edge[i].weight=w;
/*枝の両端のノード番号をセット*/
edge[i].nd1_idx=j;
edge[i].nd2_idx=k;
/*j番目のノードのリストにｋ番目のノードを追加*/
/*枝番号も渡す*/
add_node_list(&node[j],k,i);
/*k番目のノードのリストにj番目のノードを追加*/
/*枝番号も渡す*/
add_node_list(&node[j],k,i);
}
fclose(fp);
return 0;
}
/*ノードリストへ接続するノード情報の追加*/
int add_node_list(
struct node *nd,/*ノード*/
int nd_num,/*追加番号*/
int eg_num/*追加番号*/
)
{
struct node_list *nl;
nl =(struct node_list *)malloc(sizeof(struct node_l
ist));
nl->nd_idx = nd_num;
nl->eg_idx = eg_num;
nl->next = nd->nd_list;
nd->nd_list = nl;
return 0;
}
|
