Dijkstra算法源代码

Dijkstra算法源代码 很详细，有注释！可直接运行！

/*
************************Dijkstra算法*****************************************
 OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点　
1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复第2和第3步直到OPEN表为空，或找到目标点。
**************************作者：刘志平 E-mail:liuzhiping0728@163.com*********
*/
#include
#include
#define max 1000    //最大权值；权值最大时，路径不可达
#define max_node 15 //最大节点数
#define st1 “d:\\dijkstra_v4\\in.txt“  //数据存放路径
#define st2 “d:\\dijkstra_v4\\out.txt“  //结果存放路径

void main（）
{
	int ijkminnoden_s;       //node为节点数，n_s为最初顶点
	int dist[max_node][max_node]; //各路径权值，
	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）;    //读取节点数及最初顶点，初始化各路径权值
        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（“结果在：%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