最短路径算法Dijkstra源代码

最短路径算法Dijkstra源代码，测试可以正常使用

//dijkstra
#include 
#include 
using namespace std;


const int maxn = 3100;
char mystr[200];
int nmstartovercost[maxn][maxn]dist[maxn]used[maxn]way[maxn];

//////////////////////////////////
void print（int a）  //递归打印 
{  
	if （way[a]!=-1）
		print（way[a]）;
	cout << a<< “\t“;
}

///////////////////////////
int main（void）
{  
	//init
	int ijkabcmin;
	freopen（“dijk.in““r“stdin）;
	freopen（“dijk.out““w“stdout）;
	// freopen（ “CON“ “w“ stdout ）; 恢复屏幕输出
//	cout<<“input: node num start node end node“<	cin >> n >> start >> over ;
	for （i = 1; i <= n; i++）
	{
		for （j = 1; j <= n; j++）
			cost[i][j] = 0x7FFFFFFFL;
		cost[i][i] = 0;
	}
	while （!feof（stdin））
	{   
		mystr[0] = ‘\0‘;
		gets（mystr）;
		if （strlen（mystr） != 0）
		{ 
			sscanf（mystr “%d%d%d“ &a &b &c）; 
			cost[a][b] = c; 
			cost[b][a] = c; 
		}
	}
	for （i = 1;i <= n;i++）
	{  
		dist[i] = cost[start][i]; 
		used[i] = 0; 
		way[i] = start; 
	}
	//dijkstra
	used[start] = 1;
	for （i = 1; i < n; i++）
	{  
		min = 0x7FFFFFFFL;
		for （j = 1; j <= n; j++）
		{
			if （dist[j] < min && used[j] == 0）
			{ 
				min = dist[j]; 
				k = j; 
			}  // 确定下一个搜索起始的结点
		}
		used[k] = 1;
		for （j = 1; j <= n; j++）
		{
			if （min + cost[k][j] < dist[j] && cost[k][j] < 0x7FFFFFFFL）
			{ 
				dist[j] = min + cost[k][j]; 
				way[j] = k; 
			}
		}
	} //for
	//out
	cout << dist[over] << “\t“;
	way[start] = -1;
	print（over）;
	return 0;
}

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

     文件       9024  2016-06-22 16:37  Dijkstra_test\Debug\BuildLog.htm

     文件      43247  2016-06-22 16:37  Dijkstra_test\Debug\dijkstra.obj

     文件      44032  2016-06-22 16:37  Dijkstra_test\Debug\Dijkstra_test.exe

     文件        663  2016-06-22 15:31  Dijkstra_test\Debug\Dijkstra_test.exe.embed.manifest

     文件        728  2016-06-22 15:31  Dijkstra_test\Debug\Dijkstra_test.exe.embed.manifest.res

     文件        621  2016-06-22 16:37  Dijkstra_test\Debug\Dijkstra_test.exe.intermediate.manifest

     文件     433800  2016-06-22 16:37  Dijkstra_test\Debug\Dijkstra_test.ilk

     文件     560128  2016-06-22 16:37  Dijkstra_test\Debug\Dijkstra_test.pdb

     文件         65  2016-06-22 16:37  Dijkstra_test\Debug\mt.dep

     文件     166912  2016-06-22 16:37  Dijkstra_test\Debug\vc90.idb

     文件     217088  2016-06-22 16:37  Dijkstra_test\Debug\vc90.pdb

     文件         70  2016-06-22 15:48  Dijkstra_test\dijk.in

     文件         70  2016-06-22 15:41  Dijkstra_test\dijk.in.bak

     文件         10  2016-06-22 16:37  Dijkstra_test\dijk.out

     文件       1559  2016-06-22 16:40  Dijkstra_test\dijkstra.cpp

     文件    1166336  2016-06-22 16:44  Dijkstra_test\Dijkstra_test.ncb

     文件        891  2016-06-22 15:17  Dijkstra_test\Dijkstra_test.sln

    ..A..H.      8704  2016-06-22 16:44  Dijkstra_test\Dijkstra_test.suo

     文件       3932  2016-06-22 15:30  Dijkstra_test\Dijkstra_test.vcproj

     文件       1427  2016-06-22 16:44  Dijkstra_test\Dijkstra_test.vcproj.PC-20160614CKWE.Administrator.user

     目录          0  2016-06-22 16:37  Dijkstra_test\Debug

     目录          0  2016-06-22 16:40  Dijkstra_test

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

              2659307                    22