dijkstra.cpp

dijkstra算法实现

// Dijkstra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;

#define INF 10000											// 路径不可达
#define MAX	7											// 路径图中最大节点数

#define ID_BEGIN 0											// 单条路径中的开始节点
#define ID_END 1											// 单挑路径中中的结束节点

typedef vector<int> VecSinglePath;							// 单挑路径数组，存放路径节点信息
typedef vector<int>::iterator itSinglePath;					// 单挑路径迭代器

typedef vector<VecSinglePath> VecAllPath;					// 路径总表，单挑路径的汇总
typedef vector<VecSinglePath>::iterator itAllPath;			// 路径总表迭代器

typedef int DijGraph;										// 定义路径图
DijGraph g_dijGraph[MAX][MAX];								// 路径图声明，可以为无向图

/************************************************************************/
/* 初始化路径图                                                         */
/************************************************************************/
void InitDijGraph()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			g_dijGraph[i][j] = ((j == i) ? 0 : INF);		// 本身距离为0，其他为INF
		}
	}

/*
// graph 0
	g_dijGraph[0][1] = 2;
	g_dijGraph[0][2] = 3;
	g_dijGraph[0][3] = 1;
	g_dijGraph[1][2] = 1;
	g_dijGraph[1][4] = 2;
	g_dijGraph[2][4] = 1;
	g_dijGraph[3][2] = 1;
	g_dijGraph[3][4] = 3;
*/

/*
// graph 1
	g_dijGraph[0][1] = 10;
	g_dijGraph[0][3] = 100;
	g_dijGraph[0][4] = 30;
	g_dijGraph[1][2] = 80;
	g_dijGraph[1][4] = 10;
	g_dijGraph[2][3] = 10;
	g_dijGraph[4][2] = 10;
	g_dijGraph[4][3] = 80;
*/

// graph 2
	g_dijGraph[0][1] = 2;
	g_dijGraph[0][3] = 5;
	g_dijGraph[0][4] = 1;
	g_dijGraph[1][2] = 2;
	g_dijGraph[1][3] = 2;
	g_dijGraph[2][6] = 1;
	g_dijGraph[3][2] = 1;
	g_dijGraph[3][6] = 5;
	g_dijGraph[3][5] = 4;
	g_dijGraph[4][3] = 1;
	g_dijGraph[4][5] = 4;
	g_dijGraph[5][6] = 4;

	g_dijGraph[1][0] = 2;
	g_dijGraph[3][0] = 5;
	g_dijGraph[4][0] = 1;
	g_dijGraph[2][1] = 2;
	g_dijGraph[3][1] = 2;
	g_dijGraph[6][2] = 1;
	g_dijGraph[2][3] = 1;
	g_dijGraph[6][3] = 5;
	g_dijGraph[5][3] = 4;
	g_dijGraph[3][4] = 1;
	g_dijGraph[5][4] = 4;
	g_dijGraph[6][5] = 4;
}

/************************************************************************/
/* 初始化vecsinglePath和vecAllPath                                      */
/************************************************************************/
void InitDijPath(VecAllPath& vecAllPath, const int nBeginID)
{
	for (int i = 0; i < MAX; i++)
	{
		if (nBeginID == i)									// 本身跳过
		{
			continue;
		}
		else												// nBeginID到每一个节点的路径
		{
			VecSinglePath vecSinglePath;
			vecSinglePath.push_back(nBeginID);				// 开始点
			vecSinglePath.push_back(i);						// 结束点

			vecAllPath.push_back(vecSinglePath);			// 将单条路径加到路径总表vecAllPath
		}
	}
}

/************************************************************************/
/* 获取vecAllPath中索引为nIndex的那条路径								*/
/************************************************************************/
VecSinglePath GetSinglePathByIndex(VecAllPath vecAllPath, unsigned int nIndex)
{
	assert(nIndex < vecAllPath.size() && _T("边界值溢出"));
	itAllPath it_AllPath = vecAllPath.begin();
	while (nIndex--)
	{
		it_AllPath++;
	}
	return (*it_AllPath);
}

/************************************************************************/
/* 判断某点是否在该条路径中                                             */
/************************************************************************/
bool IsNodeInPath(VecSinglePath vecSinglePath, const int nNode)
{
	bool bNodeInPath = false;
	for (itSinglePath it_SinglePath = vecSinglePath.begin(); it_SinglePath != vecSinglePath.end(); it_SinglePath++)
	{// 循环单条路径中的每个节点
		if (nNode == (*it_SinglePath))
		{
			bNodeInPath = true;
			break;
		}
	}
	return bNodeInPath;
}

/************************************************************************/
/* 扩展当前路径的下个节点                                               */
/************************************************************************/
void ExpandaNode(VecAllPath& vecAllPath, VecSinglePath vecSinglePath, const int nNode)
{
	// 保存原路径信息
	int nBeginID = vecSinglePath.at(ID_BEGIN);
	int nEndID = vecSinglePath.at(ID_END);

	int nComDist = g_dijGraph[nBeginID][nEndID] + g_dijGraph[nEndID][nNode];		// 计算扩展了nNode后从nBeginID到nNode的距离
	if (nComDist < g_dijGraph[nBeginID][nNode])										// 比已经获得的路径短，则加入扩展队列
	{
		for (itAllPath it_AllPath = vecAllPath.begin(); it_AllPath != vecAllPath.end(); it_AllPath++)
		{// 循环路径总表，寻找需要更新的路径
			VecSinglePath& vecUpdatePath = (*it_AllPath);
			if (vecUpdatePath.at(ID_BEGIN) == nBeginID && vecUpdatePath.at(ID_END) == nNode)
			{// 已经找到要扩更新的路径，则更新
				vecUpdatePath.clear();
				vecUpdatePath.push_back(nBeginID);
				vecUpdatePath.push_back(nNode);
				itSinglePath it_SinglePath = vecSinglePath.begin() + ID_END;
				while ((++it_SinglePath) < vecSinglePath.end())						// 将更新的点用对应的路径替代
				{
					vecUpdatePath.push_back(*it_SinglePath);
				}
				vecUpdatePath.push_back(nEndID);
				break;
			}
		}
		g_dijGraph[nBeginID][nNode] = nComDist;
	}
}

/************************************************************************/
/* dijkstra寻路算法                                                     */
/************************************************************************/
void Dijkstra(VecAllPath& vecAllPath, const int nBeginID, const int nEndID)
{
	InitDijPath(vecAllPath, nBeginID);
	for (int nNode = 0; nNode < MAX - 2; nNode++)									// 查找需要更新的项目
	{
		for (size_t i = 0; i < vecAllPath.size(); i++)								// 沿每条路径扩展下先
		{
			VecSinglePath vecSinglePath = GetSinglePathByIndex(vecAllPath, static_cast<int>(i));
			for (int j = 0; j < MAX; j++)											// 看每个点是否可以扩展
			{
				if (!IsNodeInPath(vecSinglePath, j))								// 如果点j不在路径中,则扩展
				{
					ExpandaNode(vecAllPath, vecSinglePath, j);
				}
			}
		}
	}
}

/************************************************************************/
/* 输出结果                                                             */
/************************************************************************/
void Print(const VecAllPath vecAllPath)
{
	for (size_t i = 0; i < vecAllPath.size(); i++)
	{
		VecSinglePath vecSinglePath = GetSinglePathByIndex(vecAllPath, static_cast<int>(i));
		cout<<"Dist\t:\t"<<g_dijGraph[vecSinglePath.at(ID_BEGIN)][vecSinglePath.at(ID_END)]<<"\tPath\t:\t";
		for (itSinglePath it_SinglePath = vecSinglePath.begin(); it_SinglePath != vecSinglePath.end(); it_SinglePath++)
		{
			cout<<(*it_SinglePath);
			if (it_SinglePath != vecSinglePath.end() - 1)
			{
				cout<<"->";
			}
		}
		cout<<endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	VecAllPath vecAllPath;
	int nBeginID = 0, nEndID = 6;
	InitDijGraph();
//	cout<<"请输入开始点：";
	cin>>nBeginID>>nEndID;
//	cout<<"请输入结束点：";
//	cin>>nEndID;
//	cout<<"结果如下："<<endl;
	DWORD dwOldCnt = ::GetTickCount();
	Dijkstra(vecAllPath, nBeginID, nBeginID);
	cout<<"耗时\t：\t"<<(::GetTickCount() - dwOldCnt)<<"毫秒。"<<endl;
	Print(vecAllPath);
	cin.get();
	cin.get();
	return 0;
}