dijkstra.cpp

使用DIJKSTAR算法解决多点最短路径,还带文字解说

#include "dijkstra.h"
#include<iostream>
#include<iomanip>
using namespace std;
dijkstra::dijkstra()
{
//	town_first = NULL;	//没有用的变量
	index_start = 0;
	result = NULL;
}

dijkstra::~dijkstra()
{
}

/*
	我这里修改了该函数  以前的是将第一个 result[0] 保存为用户选中的那个城市 
	现在修改的从0开始 依次对应input文件中列举的每个城市 自己到自己的距离为0!( result[index_start] 项)
*/
RArray* dijkstra::doDijkstra(map* townmap, string* name)
{
	int i,ntown=0;
    int TownSize = townmap->getTownSize();

	//result记录每个town到指定town的最短距离
	result = new RArray[TownSize];		

	//原程序这里打印文件中读取的城市数据  这里注释掉 格式让人不容易看懂  
//	cout<<"there is the information with map: "<<endl;
//	townmap->printMap();

	//初始化。
	a.push_back(0);
	//保存每个其他城市到index_start指定城市的距离 该距离为直接距离 是使从文件中读取到的  没有处理过的
	for(i = 0; i < TownSize; i++)
	{
		if (i == index_start)
		{
			result[i].townName = townmap->getTownIndex(index_start)->getTownName();
			result[i].nearestkm = 0;
			continue;
		}

		if (i < index_start)
		{
			result[i].townName = name[i];
			result[i].nearestkm = townmap->getTownIndex(i)->getList()->getConnection(index_start-i-1)->getkm();
		}
		else
		{
			result[i].townName = name[i];
			result[i].nearestkm = townmap->getTownIndex(index_start)->getList()->getConnection(i-index_start-1)->getkm();
		}
	}

	//最短距离更新。
	//每次循环都会将都会更新 将影响到 getMinTown的结果
    while(ntown!=TownSize)
	{
		int temp = getMinTown(result, a, TownSize);
   		a.push_back(temp);
		ntown++;
		
	    if(-1 != temp) 
		{
		 double dk = result[temp].nearestkm;
		 for(i = 0; i < TownSize; i++)
		 {
			if(temp == i)
				continue;
			if(temp < i)
			{
			  if(result[i].nearestkm)
				{
				  int dk2 = townmap->getTownIndex(temp)->getList()->getConnection(i-temp-1)->getkm();
                   if(dk2)
                    if(result[i].nearestkm > dk + dk2)
					  result[i].nearestkm = dk +dk2;
				}
			  else
			  {
			     int dk2 = townmap->getTownIndex(temp)->getList()->getConnection(i-temp-1)->getkm();
				 if(dk2)
				  result[i].nearestkm = dk + dk2;
			  }  
			}
			if(temp > i)
			{
                if(result[i].nearestkm)
				{
				  int dk2 = townmap->getTownIndex(i)->getList()->getConnection(temp-i-1)->getkm();
                   if(dk2)
                    if(result[i].nearestkm > dk + dk2)
					  result[i].nearestkm = dk +dk2;
				}
			  else
			  {
			     int dk2 = townmap->getTownIndex(i)->getList()->getConnection(temp-i-1)->getkm();
				 if(dk2)
				  result[i].nearestkm = dk + dk2;
			  }  
			}
          
		 }
		
		}
		
	}

	return result;
}

void dijkstra::printResult(RArray* result1, int TownSize)
{

	RArray temp;
	int i, j, k;

	//该for循环将结果作了排序 从小到大的排序  基本没有用 
	//时间问题我没有修改这里的  如果你需要修改这里的话  记住在调换的时候
	//需要注意调换index_start的值 因为后面是根据index_start来输出的  这里排序的时候 如果没有重新
	//确定index_start被调换到那个位置上去了的话  后面输出就是错误的 
/*	for( i = 0; i < TownSize-1; i++)
	{
		k = i;
		for(j = i + 1; j < TownSize; j++)
		{
			if(result1[j].nearestkm < result1[k].nearestkm)
			{
				k = j;
			}
		}
		if(k!=i)
		{
			temp.townName = result1[i].townName;
			temp.nearestkm = result1[i].nearestkm;
			result1[i].townName = result1[k].townName;
			result1[i].nearestkm = result1[k].nearestkm;
			result1[k].townName = temp.townName;
			result1[k].nearestkm = temp.nearestkm;
		}
	}
*/
	cout<<"Shortest path from "<<result1[index_start].townName.c_str()<<" to"<<endl;
	for( i = 0; i < TownSize; i++)
	{
		if (i == index_start)
		{
			continue;
		}
		cout<<setw(20)<<left<<result1[i].townName<<result1[i].nearestkm
			<<"Km"<<endl;
	}
	cout<<"note: 0 stand for no paths!"<<endl;
}

//返回直接距离最小的城市序号
int dijkstra::getMinTown(RArray* res, vector<int> a, int TownSize)
{
	int i;
	int temp = -1, km = 0;
	for( i = 0; i < TownSize; i++)
	{
	   if(!isInA(a,i) && 0 != res[i].nearestkm)
	   {
            km = res[i].nearestkm;
	    	temp = i;
			break;
	   }
	}

	for( i = 0; i < TownSize; i++)
	{
	  if(!isInA(a,i) && 0 != res[i].nearestkm)
	   {
		if(res[i].nearestkm < km)
		{
            km = res[i].nearestkm;
	    	temp = i;
		}
	  }
	}
	return temp;
}

bool dijkstra::isInA(vector<int> a, int index)
{
	bool isIn = false;
	for(int i = 0; i < a.size(); i++)
	{
		if(index == a[i])
		{
			isIn = true;
			break;
		}
	}
	return isIn;
}