graph.h

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

#if !defined GRAPH_H
#define GRAPH_H

#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
const int max_size=100;

struct Vertex				//代表城市
{
	string name;				
	double x;
	double y;
	Vertex(double x_in, double y_in, string name_in)
	{
		x=x_in;
		y=y_in;
		name=name_in;
	}
};

class Graph
{
public:
	Graph();
	void read(string infilename);
	void write();				//输出城市信息
	void Floyd();					//Floyd算法计算任两点间最短距离
	void Dijkstra();				//Dijkstra算法计算任两点间最短距离
	void printFlights();			//输出可通的城市和两种算法分别给出的路径
	void recursive_find_path (int m,int n);
private:
	int count;
	vector<Vertex> cities;
	double distance[max_size][max_size];			//存放任两点初始距离，有正数的权值，不连通的顶点距离设为-1
	double D[max_size][max_size];						//存放Floyd算法更新的最短距离
	double D2[max_size][max_size];						//存放Dijtstra算法更新的最短距离
	int Pass[max_size][max_size];						//存放Floyd算法路径的后续点序号
	int Pass2[max_size][max_size];						//存放Dijtstra算法路径的后续点序号
};


#endif