#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算法計(jì)算任兩點(diǎn)間最短距離
	void Dijkstra();				//Dijkstra算法計(jì)算任兩點(diǎn)間最短距離
	void printFlights();			//輸出可通的城市和兩種算法分別給出的路徑
	void recursive_find_path (int m,int n);
private:
	int count;
	vector<Vertex> cities;
	double distance[max_size][max_size];			//存放任兩點(diǎn)初始距離，有正數(shù)的權(quán)值，不連通的頂點(diǎn)距離設(shè)為-1
	double D[max_size][max_size];						//存放Floyd算法更新的最短距離
	double D2[max_size][max_size];						//存放Dijtstra算法更新的最短距離
	int Pass[max_size][max_size];						//存放Floyd算法路徑的后續(xù)點(diǎn)序號(hào)
	int Pass2[max_size][max_size];						//存放Dijtstra算法路徑的后續(xù)點(diǎn)序號(hào)
};


#endif