Dijkstra算法实现天津地铁最短路径查找

希望能帮到你开发与路径有关的VC应用程序……

#include “iostream“
#include “string“
using namespace std;
#define MaxInt 100000

int stanum;//所经站点数
static bool IsT（string *name string nam int n）//检查是不是节点
{
	int i = 0;
	while （i < n） {
		if （name[i] == nam） {
			return true;
		}
		i ++;
	}
	return false;
}

int Check（string *name string nam int n）
{
	int i = 0;
	while （i < n && name[i] != nam） {
		i ++;
	}
	return i;
}

/*void Creat_path（float *Map string *name int n）
{
	cout << “请输入要添加路径的两个结点的名称：“;
	string name1 name2;
	cin >> name1 >> name2;
	if （name1 != “?“ && name2 != “?“） {
		int i j;
		
		i = Check（name “a“ n）;
		j = Check（name “e“ n）;
		Map[n * i + j] = path;
		Creat_path（Map name n）;
	
}*/

void print（int *pa string *nam int v  int i）//V表示是目地结点
{
	if （pa[i] >= 0） {
		print（pa nam vpa[i]）;
		cout<		cout <		stanum = stanum+1;
	}
}

float Dijkstra（double *Map int *path int n int vint d）
{
	float minks;
	int ut;
	float *dist = new float[n];
	int *s = new int [n];
	for（int i = 0; i < n; i ++）
	{
		dist[i] = Map[n * v + i];
		s[i] = 0;
		if （i != v && dist[i] < MaxInt） {
			path[i] = v;
		}
		else
			path[i] = -1;
	}
	s[v] = 1;
	for（i = 0; i < n - 1; i ++）
	{
		min = MaxInt;
		u = v;
		for（int j = 0; j < n; j ++）
		{
			if （!s[j] && dist[j] < min） {
				u = j;
				min = dist[j];
			}
		}
		s[u] = 1;
		for（t = 0; t < n; t ++）
		{
			if （!s[t] && dist[u] + Map[n * u + t] < dist[t]） {
				dist[t] = dist[u] + Map[n * u + t];
				path[t] = u;
			}
		}
	}
	
	ks = dist[d];//现在只返回人要的那个目的值
	return ks;
	delete dist;
}

void main（）
{
//	cout << “请输入该图的结点数：“;
	int n = 57;
//	cin >> n;
	double Map[57*57];
	double *Ma = Map;//一维数组表示二维数组的内容
	for （int i = 0; i < n * n; i ++）
		Map[i] = MaxInt;
//	cout << “请依次输入各结点的名称！“ << ‘\n‘;
	string name[57];
	string *nam = name;

	int path[57];
	int *pa=path;


		name[0] = “刘园站“;
		name[1] = “西横堤“;
		name[2] = “果酒厂“;
		name[3] = “本溪路“;
		name[4] = “勤俭道“;
		name[5] = “洪湖里“;
		name[6] = “西站“;
		name[7] = “西北角“;
		name[8] = “西南角“;
		name[9] = “二纬路“;
		name[10] = “海光寺“;
		name[11] = “鞍山道“;
		name[12] = “营口道“;
		name[13] =  “小白楼“;
		name[14] = “下瓦房“;
		name[15] = “南楼“;
		name[16] = “土城“;
		name[17] = “陈塘庄“;
		name[18] = “复兴站“;
		name[19] = “华山里“;
		name[20] = “财经大学“;
		name[21] = “双林站“;
		name[22] = “大卞庄“;
		name[23] = “芥园西里“;
		name[24] = “密云路“;
		name[25] = “咸阳路“;
		name[26] = “红旗路“;
		name[27] = “青年路“;
		name[28] = “鼓楼“;
		name[29] = “东南角“;
		name[30] = “天津站“;
		name[31] = “新开路“;
		name[32] = “红星路“;
		name[33] = “靖江路“;
		name[34] = “翠阜新村“;
		name[35] = “天山路“;
		name[36] = “南淀“;
		name[37] = “合成洗涤剂厂“;
		name[38] = “李明庄“;
		name[39] = “化苑产业园区“;
		name[40] = “天津工业大学“;
		name[41] = “华苑站“;
		name[42] = “王顶堤“;
		name[43] = “红旗南路“;
		name[44] = “水上公园“;
		name[45] = “南开大学“;
		name[46] = “西康路“;
		name[47] = “和平路“;
		name[48] = “华龙道“;
		name[49] = “小树林“;
		name[50

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7929  2009-09-05 16:35  Dijkstra\Dijkstra.cpp

     文件       3425  2009-09-05 16:33  Dijkstra\Dijkstra.dsp

     文件        539  2009-09-05 17:00  Dijkstra\Dijkstra.dsw

     文件      50176  2009-09-05 17:06  Dijkstra\Dijkstra.ncb

     文件      53760  2009-09-05 17:06  Dijkstra\Dijkstra.opt

     文件       1256  2009-09-05 16:35  Dijkstra\Dijkstra.plg

     文件        529  2008-05-03 22:19  Dijkstra\Read Me.txt

     目录          0  2009-11-26 22:13  Dijkstra\Debug

     目录          0  2009-09-05 17:06  Dijkstra

----------- ---------  ---------- -----  ----

               117614                    9