/* dijkstra.c
graph.h を同じディレクトリに download して用いよ

コンパイル命令と実行命令：
gcc dijkstra.c -o dijkstra
./dijkstra

K. Shiota
2005.6.8
*/

#define MAXORDER 256
#include "graph.h"
#include "digraph.h"

main()
{
	Graph g;		// 探索対象グラフ
	List path;		// 道順
	int startNode=0;	// 出発点	
	int goalNode;		// 目的地
	int l;			// 最短距離
	int i;

// テストデータ（プリントの例）
	int maze[6][6] = {
		{ 0, 3, 0, 3, 7, 0},
		{ 3, 0, 5, 6, 2, 7},
		{ 0, 5, 0, 0, 1, 3},
		{ 3, 6, 0, 0, 4, 0},
		{ 7, 2, 1, 4, 0, 6},
		{ 0, 7, 3, 0, 6, 0}
	};
		
// 乱数の初期化
	srand(time(NULL));

// テストデータの場合
//	g=ArraytoGraph(6,maze);

// ランダムな重み付きグラフを生成
// 引数は頂点数、辺の割合、最大重み
	g=RandomWeightedGraph(128,0.05,9);
//	g=RandomWeightedGraph(8,0.3,9);

// ランダムな重み付き有向グラフを生成
// 引数は頂点数、辺の割合、最大重み
//	g=RandomWeightedDiGraph(64,0.05,9);

	goalNode=g.ord-1;	// 目的地は最大番号
	l=Dijkstra(g,startNode,goalNode,&path);
	printf("\nGraph :\n");
	WriteGraph(g);
	// WriteWeightedGraph(g);	// 重みが 10 以上になるときはこちらを用いよ
	if(l>=0){		// 最短距離が正しく計算されていれば解あり
		printf("\nSolution : ");		
		for(i=0;i<path.len;i++){
			if(i!=0) printf(" -> ");
			printf("%d",path.mem[i]);
		}
		printf("\n");
		printf("Length = %d\n",l);
	}
	else printf("\nNo Solution\n");
}