dijkstra.cpp

这是有关数据结构的例程序

#include <iostream.h>
#include <fstream.h>
#include "Dijkstra.h"

/*  Begin of constructor CGraph  */
CGraph::CGraph(unsigned size, unsigned v)
{//初始化图
	unsigned i;

	m_Size = size;
	m_SrcVector = v;
	m_Dist = new int [m_Size];
	m_Prev = new unsigned [m_Size];

	m_S = new bool [m_Size];//存储已加入集合S的顶点
	for (i=0; i<m_Size; i++) {//刚开始集合S中没有顶点
		m_S[i] = false;
	}

	m_Graph = new int* [m_Size];
	for (i=0; i<m_Size; i++) {
		m_Graph[i] = new int [m_Size];
	}
}
/*  End of constructor CGraph  */

/*  Begin of destructor ~CGraph  */
CGraph::~CGraph()
{
	unsigned i;

	for (i=0; i<m_Size; i++) {
		delete [] m_Graph[i];
	}
	delete [] m_Graph;
	delete [] m_Dist;
	delete [] m_Prev;
	delete [] m_S;
}
/*  End of destructor ~CGraph  */

/*  Begin of function Dijkstra  */
bool CGraph::Dijkstra()//计算最短路经
{
	unsigned i, j;

	m_Dist[m_SrcVector-1] = 0;
	m_S[m_SrcVector-1] = true;
	for (i=0; i<m_Size-1; i++) {
		int temp = -1;
		bool flag = false;
		unsigned u = m_SrcVector-1;

		//找出距离最短的顶点
		for (j=0; j<m_Size; j++) {
			if ( (!m_S[j]) && (m_Dist[j]!=-1) ) {
				if (!flag) {
					u = j;
					temp = m_Dist[j];
					flag = true;
				}
				else if (m_Dist[j]<temp) {
					u = j;
					temp = m_Dist[j];
				}
			}
		}
		m_S[u] = true;//把顶点加入集合

		//调整源顶点到各顶点的最短距离
		for (j = 0; j<m_Size; j++) {
			if ( (!m_S[j]) && (m_Graph[u][j]!=-1) ) {
				int newdist = m_Dist[u] + m_Graph[u][j];
				if ( (newdist<m_Dist[j]) || (m_Dist[j]==-1) ) {
					m_Dist[j] = newdist;
					m_Prev[j] = u;
				}
			}
		}
	}

	return true;
}
/*  End of function Dijkstra  */

/*  Begin of overloaded operator <<  */
ostream& operator<<(ostream &stream, const CGraph &Graph)
{
	unsigned i, dest, start;
	int *path;//记录通过的顶点

	path = new int [Graph.m_Size];
	path[Graph.m_Size-1] = -1;

	for (dest=0; dest<Graph.m_Size; dest++) {
		start = Graph.m_Size-2;
		if ( (dest!=Graph.m_SrcVector-1) ) {//若源顶点和目的定点不同			
			if (Graph.m_Dist[dest]==-1) {//若无通路
				cout<<"顶点 "<<Graph.m_SrcVector<<" 到顶点 "<<dest+1<<" 无通路"<<endl<<endl;
			}
			else {//若有通路
				i = dest;
				while (Graph.m_Prev[i] != Graph.m_SrcVector-1 ) {
					i = Graph.m_Prev[i];
					path[start] = i;//记录通过的顶点
					start--;
				}
				//打印通路
				start++;
				cout<<"顶点 "<<Graph.m_SrcVector<<" 到顶点 "<<dest+1<<" 的最短路径为："
					<<Graph.m_SrcVector<<" —> ";
				while (path[start]!=-1) {
					cout<<path[start]+1<<" —> ";
					start++;
				}
				cout<<dest+1<<endl
					<<"距离为："<<Graph.m_Dist[dest]<<endl<<endl;
			}
		}
	}
	cout<<endl<<endl;

	delete [] path;
	return stream;
}
/*  End of overloaded operator <<  */

/*  Begin of overloaded operator >>  */
ifstream& operator>>(ifstream &fstream, CGraph &Graph)
{
	unsigned i, j;

	for (i=0; i<Graph.m_Size; i++) {//从文件读取顶点信息
		for (j=0; j<Graph.m_Size; j++) {
			fstream>>Graph.m_Graph[i][j];
		}
	}
	for (j=0; j<Graph.m_Size; j++) {//初始化源顶点到各个顶点的距离
		Graph.m_Dist[j] = Graph.m_Graph[Graph.m_SrcVector-1][j];
		if ( (Graph.m_Dist[j] != -1) && (j != Graph.m_SrcVector-1) ) {
			Graph.m_Prev[j] = Graph.m_SrcVector - 1;
		}
		else {
			Graph.m_Prev[j] = 0;
		}
	}

	return fstream;
}
/*  End of overloaded operator >>  */