实现功能：
加/减城市路径，最短算法，打印路径，遍历
（部分功能会报错）
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/* define some variables and structures */
#define MAX_VERTEXES 50 //define the max number of vertexes is 30
#define INFINITY 100000 //define the infinity value is 100000
typedef struct vertexNode
{
string cityName; //a string that store the name of city
bool available; //true means the vertex is available
bool visited;//true means the vertex has been visited
}vertexNode, vertexes[MAX_VERTEXES]; //an array of vertexes
typedef struct edgeNode
{
double weight; //the weight of the edge
bool state; //true means the edge is available
}edgeNode, edges[MAX_VERTEXES][MAX_VERTEXES]; //an array of edges
typedef struct
{
vertexes vex; //an array of vertexes
edges arc; //an array of edges
int vexcount, edgecount; //two ints that record the current number of vertexes and edges
}MGraph;
/* a class of graph that includes all operations for this assignment*/
class Graph
{
public:
Graph();
~Graph();
bool checkVertex(string vertex); //input a vertex, check the vertex is exist or not
int locationVertex(string vertex); //return the location of input vertex
void insertVertex(string vertex); //insert a vertex
void insertEdge(int l, int r, double val); //insert an edge at the position[l][r], and the weight is val
void deleteEdge(int l, int r); //delete an edge at the position[l][r]
bool checkAvailableVertex(int pos); //check the vertex is available/unavailable
bool checkAvailableEdge(int l, int r); //check the edge at position[l][r] is available/unavailable
void setVertexAvailable(int pos); //set the vertex available
void setVertexUnavailable(int pos); //set the vertex unavailable
void setEdgeAvailable(int l, int r); //set the edge at position [l][r] available
void setEdgeUnavailable(int l, int r); //set the edge at position [l][r] unavailable
void displayInOrder();//display the graph in alphabetical order
void display();//display the graph
void Dijkstra(int posStart, int posEnd); //Dijkstra's Algorithm to get the shortest path
void DFT(int start);//breadth-first traversal
int GetFirstNeighber(int start);
int GetNextNeighber(int start, int visited);
void ppath(int path[],int i,int v0); //a function used to print path
private:
MGraph mG;
};
Graph::Graph() //Constructor
{
mG.vexcount = 0;
mG.edgecount = 0; //initialize the count number of vertexes and edges become 0
for(int i=0; i<MAX_VERTEXES; i++)
{
mG.vex[i].available = false;
mG.vex[i].visited = false;
mG.vex[i].cityName = "unknow"; //initialize vertexes array
for (int j=0; j<MAX_VERTEXES; j++)
{
mG.arc[i][j].weight = INFINITY;
mG.arc[i][j].state = false; //initialize edges array
}
}
}
Graph::~Graph() //Destructor
{
}
bool Graph::checkVertex(std::string vertex) //input a vertex, check the vertex is exist or not
{
for (int i=0; i<mG.vexcount; i++)
{
if(vertex == mG.vex[i].cityName)
return true; //if find the vertex, return true
}
return false;
}
int Graph::locationVertex(std::string vertex)
{
for (int i=0; i<mG.vexcount; i++)
{
if(vertex == mG.vex[i].cityName)
return i; //if find the vertex, return the position of the vertex
}
return -1; //should never happened
}
void Graph::insertVertex(std::string vertex)
{
mG.vex[mG.vexcount].cityName = vertex; //insert a vertex
mG.vex[mG.vexcount].available = true; //set the vertex to be true
mG.vexcount++; //renew vexcount
}
void Graph::insertEdge(int l, int r, double val)
{
mG.arc[l][r].weight = val;
mG.arc[r][l].weight = val; //add weight to the edge, because the graph has no direction, so both edge should be the same
mG.arc[l][r].state = true;
mG.arc[r][l].state = true;//set both edge to be true
mG.edgecount++; //renew the count number of edges
}
void Graph::deleteEdge(int l, int r)
{
mG.arc[l][r].weight = INFINITY;
mG.arc[r][l].weight = INFINITY; //delete the edge
mG.arc[l][r].state = false;
mG.arc[r][l].state = false; //set both edges are false
mG.edgecount--; //renew the count number of edges
}
bool Graph::checkAvailableVertex(int pos)
{
return mG.vex[pos].available;
}
bool Graph::checkAvailableEdge(int l, int r)
{
return mG.arc[l][r].state;
}
void Graph::setVertexAvailable(int pos)
{
mG.vex[pos].available = true;
}
void Graph::setVertexUnavailable(int pos)
{
mG.vex[pos].available = false;
}
void Graph::setEdgeAvailable(int l,int r)
{
mG.arc[l][r].state = true;
mG.arc[r][l].state = true;
}
void Graph::setEdgeUnavailable(int l,int r)
{
mG.arc[l][r].state = false;
mG.arc[r][l].state = false;
}
void Graph::displayInOrder() //display the graph
{
vector<string> vect,v; //declare
for (int i=0; i<mG.vexcount; i++)
{
if (mG.vex[i].available)
vect.push_back(mG.vex[i].cityName);
}
sort(vect.begin(),vect.end());//sort the vector
for(int j=0; j<mG.vexcount; j++)
{
for(int k=0; k<mG.vexcount; k++)
{
if(mG.vex[k].cityName == vect[j])
{
v.clear();
cout<<endl<<"The route for: "<<mG.vex[k].cityName<<endl;
for (int m=0; m<mG.vexcount; m++)
{
if(mG.arc[k][m].state && mG.vex[m].available)
{
v.push_back(mG.vex[m].cityName);
}
}
sort(v.begin(),v.end());
for (int n=0; n<v.size(); n++)
{
for(int o=0;o<mG.vexcount;o++)
{
if(mG.vex[o].cityName == v[n])
cout<<"--"<<mG.arc[k][o].weight<<"->"<<mG.vex[o].cityName<<endl;
}
}
}
}
}
}
void Graph::display() //display the graph
{
for (int i=0; i<mG.vexcount; i++)
{
for (int j=0; j<mG.vexcount; j++)
{
if(mG.arc[i][j].weight != INFINITY)
{
cout<<mG.vex[i].cityName; //display city name.
if(!mG.vex[i].available)
cout<<" (Unavailable)";
cout<<" -> "<<mG.arc[i][j].weight;
if(!mG.arc[i][j].state)
cout<<" (Unavailable)";
cout<<" -> "<<mG.vex[j].cityName<<endl;
}
}
}
}
void Graph::Dijkstra(int posStart, int posEnd)
{
double dis[MAX_VERTEXES];//dis[i] is the length of shortest path from posStart to i;
int path[MAX_VERTEXES]; //path[i] store the index of the previous vertex which in the current
//shortest path between posStart and i
int s[MAX_VERTEXES]; //the shortest path that has been found from posStart
int i,j,u;
double mindis;
for(i=0;i<mG.vexcount;i++) //initialize distance
{
if(mG.arc[posStart][i].state) //check the edge is available or not
{
dis[i]=mG.arc[posStart][i].weight;
s[i]=0;
if(mG.arc[posStart][i].weight<INFINITY)
{
path[i]=posStart;
}
else
{
path[i]=-1;
}
}
}
s[posStart]=1;
path[posStart]=0;
for(i=0;i<mG.vexcount;i++) //choose the vertex that not in array s, but has a shortest distance
{
mindis=INFINITY;
u=-1;
for(j=0;j<mG.vexcount;j++)
{
if(s[j]==0&&dis[j]<mindis)
{
u=j;
mindis=dis[j];
}
}
s[u]=1;
for(j=0;j<mG.vexcount;j++) //renew the distance of vertexes that not in the array s
{
if(s[j]==0)
{
if(mG.arc[u][j].weight<INFINITY && dis[u]+mG.arc[u][j].weight<dis[j] && mG.arc[u][j].state)
{
dis[j]=dis[u]+mG.arc[u][j].weight;
path[j]=u;
}
}
}
}
if(s[posEnd]==1)//check the endpoint has a shortest path or not
{
cout<<"The length of shortest path from "<<mG.vex[posStart].cityName<<" to "<<mG.vex[posEnd].cityName<<" is: "<<dis[posEnd]<<" ";
cout<<mG.vex[posStart].cityName<<" ";
ppath(path,posEnd,posStart); //print the path
cout<<mG.vex[posEnd].cityName<<endl;
}else{
cout<<"The shortest path from "<<mG.vex[posStart].cityName<<" to "<<mG.vex[posEnd].cityName<<" does not exist\n";
}
}
void Graph::DFT(int start)
{
if(mG.vex[start].available&&!mG.vex[start].visited) //check the vertex is available or not
{
cout<<mG.vex[start].cityName<<" ";
mG.vex[start].visited = true;
int w = GetFirstNeighber(start);
while (w!=-1)
{
if(!mG.vex[w].visited)
{
DFT(w);
}
w = GetNextNeighber(start,w);
}
}
}
int Graph::GetFirstNeighber(int start)
{
if(start != -1)
{
for(int col = 0;col<mG.vexcount;col++)
{
if(mG.arc[start][col].weight!=INFINITY && mG.arc[start][col].state) //check the edge is available or not
return col;
}
}
return -1; //otherwise return -1;
}
int Graph::GetNextNeighber(int start, int visited)
{
if(start != -1&&visited!=-1)
{
for(int col= visited +1;col<mG.vexcount;col++)
{
if(mG.arc[start][col].weight!=INFINITY && mG.arc[start][col].state) //check the edge is available or not
return col;
}
}
return -1; //otherwise return -1;
}
void Graph::ppath(int path[],int i, int v0)
{
int k;
k=path[i];
if(k==v0) return;
ppath(path,k,v0);
cout<<k<<" ";
}
/*main function*/
int main()
{
ifstream inFile;
Graph g;
string city1, city2;//two cities' name
double dis; //the distance between two cities
int pos1, pos2; //the position of city1 and city2
int choose;
string input1, input2;
inFile.open("network.txt");//open a file.
if (inFile.fail()) //if open file failed
{
cout<<"The txt file open failed!"<<endl;
exit(1);
}
while(!inFile.eof())//add data into graph
{
getline(inFile,city1,' '); //put the string into city1
if(!g.checkVertex(city1)) //if the city1 is not in the graph
g.insertVertex(city1); //insert city1
getline(inFile,city2,' '); //put the string into city2
if(!g.checkVertex(city2))
g.insertVertex(city2); // same to city2
inFile>>dis;
pos1 = g.locationVertex(city1);//returen the position of city1
pos2 = g.locationVertex(city2); //return the position of city2
g.insertEdge(pos1, pos2, dis); //add an edge
}
cout<<"The graph has been created!"<<endl;
cout<<"*************************************************"<<endl
<<"************ WELCOME TO THIS PROGRAM ************"<<endl
<<"**** Authors: Sun, Jian/100285100 ************"<<endl
<<"**** Tawadrous, Mina/100326284 *******"<<endl
<<"*************************************************"<<endl
<<"*************************************************"<<endl<<endl;
do
{
cout<<"In this program, you can do:"<<endl
<<"1. add an edge into the graph."<<endl
<<"2. delete an edge into the graph."<<endl
<<"3. set an vertex unavailable."<<endl
<<"4. set an vertex available."<<endl
<<"5. set an edge unavailable."<<endl
<<"6. set an edge available."<<endl
<<"7. display graph"<<endl
<<"8. display graph in alphabetical order."<<endl
<<"9. find the shortest path between two cities."<<endl
<<"10.show all available pathes."<<endl
<<"11.quit."<<endl;
cin>>choose;
switch (choose)
{
case 1:
cout<<"Please input the first city's name:"<<endl;
cin>>input1;
cout<<"Please input the second city's name:"<<endl;
cin>>input2;
if(g.checkVertex(input1)&&g.checkVertex(input2))//make sure the two vertexes are in the graph
{
pos1 = g.locationVertex(input1);
pos2 = g.locationVertex(input2);
cout<<"Please input the weight of the edge:"<<endl;
cin>>dis;
g.insertEdge(pos1,pos2,dis);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 2:
cout<<"Please input the first city's name:"<<endl;
cin>>input1;
cout<<"Please input the second city's name:"<<endl;
cin>>input2;
if(g.checkVertex(input1)&&g.checkVertex(input2))//make sure the two vertexes are in the graph
{
pos1 = g.locationVertex(input1);
pos2 = g.locationVertex(input2);
g.deleteEdge(pos1,pos2);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 3:
cout<<"Please input the city's name:"<<endl;
cin>>input1;
if(g.checkVertex(input1))
{
pos1 = g.locationVertex(input1);
g.setVertexUnavailable(pos1);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 4:
cout<<"Please input the city's name:"<<endl;
cin>>input1;
if(g.checkVertex(input1))
{
pos1 = g.locationVertex(input1);
g.setVertexAvailable(pos1);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 5:
cout<<"Please input the first city's name:"<<endl;
cin>>input1;
cout<<"Please input the second city's name:"<<endl;
cin>>input2;
if(g.checkVertex(input1)&&g.checkVertex(input2))//make sure the two vertexes are in the graph
{
pos1 = g.locationVertex(input1);
pos2 = g.locationVertex(input2);
g.setEdgeUnavailable(pos1,pos2);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 6:
cout<<"Please input the first city's name:"<<endl;
cin>>input1;
cout<<"Please input the second city's name:"<<endl;
cin>>input2;
if(g.checkVertex(input1)&&g.checkVertex(input2))//make sure the two vertexes are in the graph
{
pos1 = g.locationVertex(input1);
pos2 = g.locationVertex(input2);
g.setEdgeAvailable(pos1,pos2);
cout<<"Successful!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 7:
g.display();
cout<<"This is the graph, vertexes are not in alphabetical order."<<endl;
cout<<"*****************************"<<endl;
break;
case 8:
g.displayInOrder();
cout<<"This is the graph, vertexes are alphabetical order."<<endl;
cout<<"*****************************"<<endl;
break;
case 9:
cout<<"===================================="<<endl
<<"======== T_T ======== T_T =========="<<endl
<<"= Sorry for this part... ==========="<<endl
<<"= But we are try to do the best... ="<<endl
<<"= Unfortunately... ================="<<endl
<<"= It still doesn't work.. T_T ======"<<endl
<<"===================================="<<endl;
cout<<"Please input the first city's name:"<<endl;
cin>>input1;
cout<<"Please input the second city's name:"<<endl;
cin>>input2;
if(g.checkVertex(input1)&&g.checkVertex(input2))
{
pos1 = g.locationVertex(input1);
pos2 = g.locationVertex(input2);
g.Dijkstra(pos1,pos2);
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 10:
cout<<"Please input the city's name:"<<endl;
cin>>input1;
if(g.checkVertex(input1))
{
pos1 = g.locationVertex(input1);
if(g.checkAvailableVertex(pos1))
{
g.DFT(pos1);
cout<<endl;
}
else
cout<<"This city is unavailable,please try again!"<<endl;
}
else
{
cout<<"invalid input, please try again"<<endl;
}
cout<<"*****************************"<<endl;
break;
case 11:
cout<<"Thank you for using this program!"<<endl;
cout<<"*****************************"<<endl;
break;
default: cout<<"That's not a choice!"<<endl;
}
cout<<endl<<endl;
}while(choose != 11);
return 0;
}
Tools 
