graph.cpp

分别用floyd 和dijkstra算法计算城市间最短路径的简单例子

#include <vector>
#include <queue>
#include<stack>
#include <fstream>
#include <iostream>
#include <string>
#include <cmath>
#include "graph.h"
using namespace std;

Graph::Graph()
{
	count=0;
	for(int i=0; i<max_size; i++)
	{
		for(int j=0; j<max_size; j++)
			distance[i][j]=-1;
	}
}

void Graph::read(string infilename)
{
	ifstream infile;
	infile.open(infilename.c_str());
	if (infile.fail())
	{
		cout<<"File open fail!\n";
	}
	char Text;
	double distanceX;
	double distanceY;
	infile.get(Text);

	while(Text!='&')
	{
		string cityname="";
		while (Text!='#'&&Text!='&')
		{
			if (Text==' ')
			{
				infile.get(Text);
				if (Text=='#')
					break;
				else
					cityname=cityname+' '+Text;
			}
			else{
				if(Text!='\n')
					cityname=cityname+Text;
			}
			infile.get(Text);
		}

		if(cityname!="")
		{
			infile>>distanceX;
			infile>>distanceY;
			cities.push_back(Vertex(distanceX, distanceY, cityname));
			count++;
		}
		infile.get(Text);
	}

	while(Text=='&')
	{
		infile.get(Text);
	}
	
	string citynameA, citynameB;

	while(!infile.eof())
	{
		citynameA="";
		citynameB="";
		while (Text!='#')
		{
			if (Text==' ')
			{
				infile.get(Text);
				if (Text=='#')
					break;
				else
					citynameA=citynameA+' '+Text;
			}
			else
			{
				if(Text!='\n')
					citynameA=citynameA+Text;
			}
			infile.get(Text);
		}
				
		infile.get(Text);
		if (Text==' ')
			infile.get(Text);
		while (Text!='#'&&Text!='\n')
		{
			if (Text==' ')
			{
				infile.get(Text);
				if (Text=='#')
					break;
				else
					citynameB=citynameB+' '+Text;
			}
			else
			{
				if(Text!='\n')
					citynameB=citynameB+Text;
			}
			infile.get(Text);
		}

		infile.get(Text);
		for(int i=0; i<count; i++)
		{
			if(cities[i].name==citynameA)
			{
				for(int j=0; j<count; j++)
				{
					if(cities[j].name==citynameB)
						distance[i][j]=sqrt((cities[i].x-cities[j].x)*(cities[i].x-cities[j].x)+(cities[i].y-cities[j].y)*(cities[i].y-cities[j].y));
				}
			}
		}
		infile.get(Text);
	}
		infile.close();
}

void Graph::write()
{
	cout<<"\nCities:\n";
	for (int i=0; i<count; i++)
	{
		cout<<"Name: "<<cities[i].name<<" position: ("<<cities[i].x<<", "<<cities[i].y<<")\n";
		for(int j=0; j<count; j++)
		{
			if(distance[i][j]!=-1)
			{
				cout<<"To: "<<cities[j].name<<endl;
			}
		}
	}
}

void Graph::Floyd ()
{
	int i=0, j=0, k=0;
	for (i=0;i<count;i++)
	{
		for (j=0; j<count; j++)
		{
			D[i][j]=distance[i][j];
			Pass[i][j]=j;
		}
	}
	for (k=0;k<count;k++)
	{
		for (i=0;i<count;i++)
		{
			for (j=0;j<count;j++)
			{
				if (D[i][k]!=-1 && D[k][j]!=-1&&i!=j)
				{
					if (D[i][j]==-1 || D[i][j]>(D[i][k]+D[k][j]))
					{
						D[i][j]=D[i][k]+D[k][j];
						Pass[i][j]=k;
					}
				}
			}
		}
	}
}

void Graph::printFlights()
{
	cout<<"\nFlights:\n";
	for(int i=0; i<count; i++)
	{
		for(int j=0; j<count; j++)
		{
			if(D[i][j]>0)
			{
				cout<<endl<<"From "<<cities[i].name<<" to "<<cities[j].name<<":\n";
				cout<<"Floyd: "<<D[i][j]<<endl;
				recursive_find_path (i,j);

			}

			if(D2[i][j]>0)
			{
				cout<<"Dijkstra: "<<D2[i][j]<<endl;
				queue<int> passage2;
				int k=i;
				
				while(Pass2[k][j]!=j)
				{
					passage2.push(Pass2[k][j]);
					k=Pass2[k][j];
				}
				passage2.push(j);

				int temp=i;
				while(!passage2.empty())
				{
					cout<<cities[temp].name<<"->"<<cities[passage2.front()].name<<":"<<D[temp][passage2.front()]<<endl;
					temp=passage2.front();
					passage2.pop();
				}
			}
		}
	}
}

void Graph::Dijkstra()
{
	int i, j, v, w;
	bool flag=false, found[max_size][max_size];
	for (i=0; i<count;i++)
	{
		for (j=0; j<count; j++)
		{
			found[i][j]=false;
			D2[i][j]=distance[i][j];
			Pass2[i][j]=j;
		}
	}
	for( i=0; i<count; i++)
	{
		found[i][i]=true;
		for( int j=0; j<count; j++)
		{
			double min=-1;
			for( w=0; w<count; w++)
			{
				if(!found[i][w]&& (min==-1 || (D2[i][w] < min && D2[i][w]>0)))
				{
					v=w; 
					flag=true; 
					min =D2[i][w];
				}
			}
			if(flag)
			{
				found[i][v]=true;
				for(int x=0; x<count; x++)
				{
					if(!found[i][x] && min!=-1 && D2[v][x]!=-1 &&( D2[i][x]==-1 ||  min + D2[v][x] < D2[i][x]))
					{
						D2[i][x]=min +D2[v][x];
						Pass2[i][x]=v;
					}
				}
				flag=false;
			}
		}
	}
}

void Graph::recursive_find_path(int m, int n)
{
	int temp=Pass[m][n];
	if (n==temp)
		cout<<cities[m].name<<"->"<<cities[n].name<<":"<<D[m][n]<<endl;
	if (n!=temp)
	{
		recursive_find_path(m,temp);
		recursive_find_path(temp,n);
	}
}