/*
************************Dijkstra算法*****************************************
?OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點　
1．?訪問路網(wǎng)中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2．?從OPEN表中找出距起始點最近的點，找出這個點的所有子節(jié)點，把這個點放到CLOSE表中。
3．?遍歷考察這個點的子節(jié)點。求出這些子節(jié)點距起始點的距離值，放子節(jié)點到OPEN表中。
4．?重復(fù)第2和第3步直到OPEN表為空，或找到目標點。
**************************作者：劉志平?E-mail:liuzhiping0728@163.com*********
*/
#include
#include
#define?max?1000????//最大權(quán)值；權(quán)值最大時，路徑不可達
#define?max_node?15?//最大節(jié)點數(shù)
#define?st1?“d:\\dijkstra_v4\\in.txt“??//數(shù)據(jù)存放路徑
#define?st2?“d:\\dijkstra_v4\\out.txt“??//結(jié)果存放路徑

void?main（）
{
	int?ijkminnoden_s;???????//node為節(jié)點數(shù)，n_s為最初頂點
	int?dist[max_node][max_node];?//各路徑權(quán)值，
	int?path[max_node][max_node];?//路徑頂點圖
	int?m_d[max_node];????????????//最短路徑min_destination?
	bool?flag[max_node];??????????//用于標識頂點是否加入S集
	FILE?*fp;

	if（（fp=fopen（st1“r“））==NULL）
	{
		printf（“Cant‘t?open?file“）;
			exit（1）;
	}
	????fscanf（fp“%d?%d“&node&n_s）;????//讀取節(jié)點數(shù)及最初頂點，初始化各路徑權(quán)值
????????for（i=0;i????????????for（j=0;j????		{
????????????????fscanf（fp“%d“&dist[i][j]）;
????		}
		}
		fclose（fp）;?


	for（i=0;i	{
		for（j=1;j		{
			path[i][j]=max;
		}
		path[i][0]=n_s;
	}

	for（i=0;i		{???
		if（dist[n_s][i]		{
			?m_d[i]=dist[n_s][i];
			?path[i][1]=i;
		}
		else?
		{
			m_d[i]=max;
		}
		????flag[i]=false;
		}

	for（k=0;k	{	
		int?temp;
		temp=0;
		flag[n_s]=true;?min=max;?//把最初頂點加入S集中

		for（i=0;i			if（（!flag[i]）&&（m_d[i]			{
				min=m_d[i];temp=i;
			}
		flag[temp]=true;

		for（j=0;j		{
			if（（!flag[j]）&&（m_d[temp]+dist[temp][j]）			{
				m_d[j]=m_d[temp]+dist[temp][j];
				for（i=0;i				{
					if（path[temp][i]					{
						path[j][i]=path[temp][i];
					}
					else
					{
						path[j][i]=j;
						break;
					}
				}
			}
		}
	}

	if（（fp=fopen（st2“a“））==NULL）
	?{
????????printf（“Can‘t?open?file“）;
????????exit（1）;
????}
	for（i=0;i		if（i!=n_s）?
		{
			if（m_d[i]			{?
				fprintf（fp“v%d->v%d:%d\t路徑：“n_sim_d[i]）;
				for（j=0;j				{
					if（path[i][j]					{
						fprintf（fp“—>v%d“path[i][j]）;
					}
					else
					{
						fprintf（fp“\n“）;
						break;
					}
				}
			}
			else
			{fprintf（fp“v%d->v%d:\t不可達\n“n_si）;}
		}

		fprintf（fp“\n“）;
		printf（“結(jié)果在：%s\t“st2）;
		fclose（fp）;
}

/*
in.txt
6
0
1000?1000?10?1000?30?100
1000?1000?5?1000?1000?1000
1000?1000?1000?50?1000?1000?
1000?1000?1000?1000?1000?10
1000?1000?1000?20?1000?60
1000?1000?1000?1000?1000?1000

out.txt

v0->v1:	不可達
v0->v2:10	路徑：—>v0—>v2
v0->v3:50	路徑：—>v0—>v4—>v3
v0->v4:30	路徑：—>v0—>v4
v0->v5:60	路徑：—>v0—>v4—>v3—>v5

*/

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????188460??2011-10-03?21:55??dijkstra_v4\Debug\di.exe

?????文件?????198988??2011-10-03?21:55??dijkstra_v4\Debug\di.ilk

?????文件???????6089??2011-10-03?21:55??dijkstra_v4\Debug\di.obj

?????文件?????223220??2011-10-03?21:22??dijkstra_v4\Debug\di.pch

?????文件?????467968??2011-10-03?21:49??dijkstra_v4\Debug\di.pdb

?????文件??????33792??2011-10-03?21:56??dijkstra_v4\Debug\vc60.idb

?????文件??????53248??2011-10-03?21:49??dijkstra_v4\Debug\vc60.pdb

?????文件???????3209??2011-10-03?21:49??dijkstra_v4\di.cpp

?????文件???????3353??2011-10-03?21:55??dijkstra_v4\di.dsp

?????文件????????527??2011-10-03?21:55??dijkstra_v4\di.dsw

?????文件??????41984??2011-10-03?21:56??dijkstra_v4\di.ncb

?????文件??????53760??2011-10-03?21:56??dijkstra_v4\di.opt

?????文件????????726??2011-10-03?21:55??dijkstra_v4\di.plg

?????文件????????177??2011-10-03?21:21??dijkstra_v4\in.txt

?????文件????????145??2011-10-03?21:56??dijkstra_v4\out.txt

?????目錄??????????0??2011-10-03?21:49??dijkstra_v4\Debug

?????目錄??????????0??2011-10-03?21:56??dijkstra_v4

-----------?---------??----------?-----??----

??????????????1275646????????????????????17