/******************************************************************************************************************************/
/*                                    實現(xiàn)尋找兩點間最短帶權(quán)路徑的Dijkstra算法                                                */
/*                                  使用鄰接矩陣表示帶權(quán)圖，并用鏈表儲存矩陣數(shù)據(jù)                                              */  
/******************************************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "link_list.h"


float element(List *list,int row,int col);
int contd(List *D,int node);
float neardist(int *lastnode,List *adjacent,List *D,int i);
int allcontd(List *adjacent,List *D);
void quit();
void prtpath(List *path,int i,int sersp);
int searchlast(List *path,int i);
void showmsg();


void main()
{
	int i = 0,j,flag = 0,dim,sersp,lastnode = -1;
	float temp,least,temp1,temp2;
	char c = ' ';

	List adjacent;
	List D;
	List path;

	CreateList(&adjacent);
	CreateList(&D);
	CreateList(&path);
	FILE *fp;

	showmsg();

	if((fp = fopen("adjacent.dat","r")) == NULL)
	{
		printf("打開文件錯誤!\n");
		quit();
	}

	while (!feof(fp))                                                                                 //從文件讀取鄰接矩陣數(shù)據(jù)
	{
		fscanf(fp,"%f,",&temp);
		InsertList(temp,i++,&adjacent);
	}

	fclose(fp);

	for(j = 0;j * j <= i;j++)
		if (i == j * j)
			flag++;

	if(!flag)
	{
		printf("鄰接矩陣必須是方陣，請重新輸入!\n");
		quit();
	}
	
	dim = sqrt(i);
	flag=0;

	for(i = 0;i < dim - 1;i++)
		for(j = i + 1;j < dim;j++)
			if(GetList(i * dim + j,&adjacent)!=GetList(j * dim + i,&adjacent))
				flag++;

	if(flag)
	{
		printf("鄰接矩陣必須是對稱矩陣，請重新輸入!\n");
		quit();
	}

	printf("輸入源結(jié)點 P 的編號:\n");
	scanf("%d",&sersp);

	while(sersp > dim || sersp <= 0)
	{
		printf("超出范圍，重新輸入:\n");
		scanf("%d",&sersp);
	}

	sersp--;

	for(i = 0;i < dim;i++)
		InsertList((i == sersp)?0:(-1),i,&D);

	flag=0;

	while(!allcontd(&adjacent,&D))                                                                //尋找鄰接到源點的最短路徑長度
	{
		for(i = 0;i < dim;i++)
			if(!contd(&D,i))
			{
				temp1 = temp2;
				if((temp2 = neardist(&lastnode,&adjacent,&D,i)) == -2)
					temp2 = temp1;
				if(flag)
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				if(neardist(&lastnode,&adjacent,&D,i) != -2)
					flag = 1;
			}
		if(flag)
		{
			least = temp2;
			flag = 0;
			for(j = 0;j < dim;j++)
			{
				if(neardist(&lastnode,&adjacent,&D,j) == least)
				{
					SetPosition(j,&D) -> entry = least;
					if(lastnode != -1)
					{
						InsertList(j,0,&path);
						InsertList(lastnode,0,&path);
					}
				}
			}
		}
	}

	for(i = 0;i < dim;i++)
		if(i != sersp)
		{
			if((int)GetList(i,&D) != -1)
			{
				printf("節(jié)點 %d 到節(jié)點 %d 的最短帶權(quán)路徑長度是: %g.\n",sersp + 1,i + 1,GetList(i,&D));
				prtpath(&path,i,sersp);
			}
			else
				printf("節(jié)點 %d 到節(jié)點 %d 沒有路連接.\n",sersp + 1,i + 1);
		}

	quit();
}

/**********************************************返回鄰接矩陣中某個元素的值*****************************************************/
float element(List *list,int row,int col)
{
	int dim;
	dim = sqrt(ListSize (list));
	return(GetList(row * dim + col,list));
}

/*******************************************判斷給定的節(jié)點是否已鄰接到源節(jié)點P*************************************************/
int contd(List *D,int node)
{
	return((int)GetList(node,D) >= 0);
}

/************************************計算給定節(jié)點到源節(jié)點P的最短路徑，如果不存在那返回 -2 ************************************/
float neardist(int *lastnode,List *adjacent,List *D,int i)
{
	int dim,j,flag = 0;
	float temp1,temp2 = -2;
	dim = ListSize(D);
	*lastnode=-1;

	for(j = 0;j < dim;j++)
		if(contd(D,j))
			if((int)element(adjacent,i,j) != -1)
			{
				temp1 = temp2;
				temp2 = element(adjacent,i,j) + GetList(j,D);
				if(flag)
				{
					if (temp2 < temp1)
						*lastnode = j;
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				}
				else
					*lastnode = j;
				flag = 1;
			}

	return temp2;
}

/***************************************判斷是否所有能夠連接的的節(jié)點都已連接到源節(jié)點P*****************************************/
int allcontd(List *adjacent,List *D)
{
	int i,flag = 0,lastnode;

	for(i = 0;i < ListSize(D);i++)
		if(!(contd(D,i)))
			if((int)neardist(&lastnode,adjacent,D,i) != -2)
			{
				flag = 1;
				break;
			}

	return !flag;
}

/***********************************************尋找源點P到已知節(jié)點經(jīng)過的路徑*************************************************/
void prtpath(List *path,int i,int sersp)
{
	int j = i;
	List way;
	CreateList(&way);
	InsertList(sersp,0,&way);
	while(searchlast(path,j) != sersp)
	{
		InsertList(searchlast(path,j),1,&way);
		j = searchlast(path,j);
	}
	printf("    路徑是: %d",sersp + 1);
	for(j = 1;j < ListSize(&way);j++)
		printf(" -> %d",(int)GetList(j,&way) + 1);
	printf(" -> %d\n",i + 1);


}

/************************************************尋找已知結(jié)點的上一個節(jié)點***************************************************/
int searchlast(List *path,int i)
{
	int position;
	for(position = 1;position < ListSize(path);position += 2)
	{
		if(GetList(position,path) == i)
			break;
	}
	return (int)GetList(position - 1,path);
}

void quit()
{
	char c;
	while (c != '\n')
		c = getchar();
	c = getchar();
	exit(1);
}

void showmsg()
{
	printf("********本程序用Dijkstra算法尋找已知圖中從源點P到其他各點的最短帶權(quán)路徑*********\n");
	printf("請將圖的鄰接矩陣輸入文件adjacent.dat,用-1表示沒有連接，然后執(zhí)行程序.\n\n\n");
}