CS106B Assignment #7: Pathfinder
Pathfinder
任务:给出一个存了地点和距离的文本,求出最短路径和最小生成树
核心要解决的问题包括:
graph类的设定,文件的输入,PQueue辅助类的建立(上节已做),最短路径的算法,最小生成树的算法
1. Graph类
使用了很多已有的数据结构,因为nodeT 和 arcT互相包含,所以要用前向引用。
#ifndef MYPATHFINDER_GRAPH_H
#define MYPATHFINDER_GRAPH_H
#include "set.h"
#include "map.h"
struct nodeT; //前向引用
struct arcT;
struct coordT
{
double x;
double y;
};
struct graphT
{
Set<nodeT *>nodes;
Set<arcT *>arcs;
Map<nodeT *>nodeMap;
};
struct nodeT
{
string name;
coordT xy;
Set<arcT *>arcs;
};
struct arcT
{
nodeT *start;
nodeT *finish;
double cost;
};
class Graph
{
public:
Graph();
~Graph();
void clear();
void addCity(string name, double x, double y);
void addFlight(string start, string end, double cost);
Set<nodeT *>::Iterator itrNodes();
Set<arcT *>::Iterator itrArcs();
Map<nodeT *>::Iterator itrMapNodes();
Set<arcT *>getArcSet();
Set<nodeT *>getNodeSet();
Map<nodeT *>getNodeMap();
void print();
private:
void addArc(nodeT* start, nodeT*end, double cost);
graphT *g;
};
#endif //MYPATHFINDER_GRAPH_H
2. 最短路径算法:Dijkstra
一种贪心算法:不断求出最短路径
基本步骤:
PQueue(出队时优先出最小的)中存放路径,Map存放已经找到最短路径的点,path是中间量 初始为空。
1. 起始点
2. 找所有起始点 连接的点
3. 对所有 连接的点 进行操作:若点不在Map中,则 path+弧 存入PQueue中
4. path = dePQueue(), 将该路径结尾的点加入Map中,该路径即为到达该点的最短路径
如果该点是要求的结尾点,则结束;否则回到 步骤1 并将该点作初始点。
一些解释:
1. 可以发现每次循环都会找到 到一个点的最短路径
2. 每个点最多只遍历到一次,因为一旦遍历到就说明找到了到它的最短路径,后面就不予考虑。
三. 最小生成树算法:Kruskal
简而言之:不断加入最短边
基本步骤:
PQueue存放弧,vector存放点的集合,minTree存最小树需要的弧
1. 把弧全部输入PQueue中,把 每个点 单独 做为一个set 存入vector中
2. dePQueue()即输出最短弧,找到该弧的 起始点 和 结束点 的标签(vector的索引)
3. 如果标签不一样,则将该弧存入minTree, 起始点和结束点所在的set合并,回到步骤2
如果标签一样, 直接回到步骤2
4. 当PQueue为空,即把所有弧全部遍历一遍时 ,算法结束
一些解释:
1. 这个算法还是比较容易理解,就是加入最短的边,前提的是 该边的两头 之前没有被连在一起
因此之前每个点都单独存一个set,边加入后,两个set合并(即连在一起)。
2. 每条弧只考虑一次
四. 完整代码
#include <iostream>
#include "pqheap.h"
#include "graph.h"
#include "set.h"
#include "map.h"
#include "simpio.h"
#include <fstream>
#include "genlib.h"
#include "strutils.h"
using namespace std;
string nextToken(ifstream &inn)
{
string line;
inn >> line;
return line;
}
void readArcs(Graph &graph, ifstream &inn)
{
while(!inn.fail())
{
string start = nextToken(inn);
string end = nextToken(inn);
if (end == "") return;
double cost = StringToReal(nextToken(inn));
graph.addFlight(start,end,cost);
}
}
void readFile(Graph &graph, ifstream &inn)
{
while (!inn.fail())
{
string line = nextToken(inn);
if (line == "NODES")
{
line = nextToken(inn);
}
else if (line == "ARCS")
{
readArcs(graph,inn);
return;
}
string city = line;
double xCoord = StringToReal(nextToken(inn));
double yCoord = StringToReal(nextToken(inn));
graph.addCity(city, xCoord, yCoord);
}
}
void loadGraphFile(Graph &graph)
{
ifstream inn;
while(true)
{
cout << "Enter name of graph data file: ";
string filename = GetLine();
inn.open("/Users/elwg/ClionProjects/mypathfinder/"+filename);
if(inn.good())
break;
cout << "Invalid file. Try again." << endl;
inn.clear();
}
readFile (graph ,inn);
inn.close();
}
int menu()
{
while(true)
{
cout << "Your options are: " << endl;
cout << " (1) Choose a new graph file" << endl <<
" (2) Find shortest path using Dijkstra's algorithm" << endl <<
" (3) Compute the minimal spanning tree using Kruskal's algorithm" << endl <<
" (4) Quit" << endl << "Enter Selection: ";
int choice = GetInteger();
if (choice >= 1 && choice <= 4) return choice;
cout << "Invalid choice. Try again." << endl;
}
}
double TotalPathDistance(Vector<arcT *> path)
{
double distance = 0;
for (int i = 0; i < path.size(); i++)
{
distance += path[i]->cost;
}
return distance;
}
//比较路径长短,因为使得队列输出最小值,所有和以前设定相反
int pathCmp(Vector<arcT *> a, Vector<arcT *> b)
{
double aCost = TotalPathDistance(a);
double bCost = TotalPathDistance(b);
if (aCost > bCost) return -1;
else if (bCost > aCost) return 1;
return 0;
}
Vector<arcT *> FindShortestPath(nodeT *start, nodeT *finish)
{
Vector<arcT *> path;
PQueue<Vector<arcT *> > queue(pathCmp); //queue存所有的最短路径
Map<double> fixed; //存放已求出的最短路径的节点,值为路径长度
while (start != finish)
{
if (!fixed.containsKey(start->name))
{
fixed.add(start->name, TotalPathDistance(path)); //start节点最短路径为0,直接放入
Set<arcT *>::Iterator itr = start->arcs.iterator(); //start连接的弧
while(itr.hasNext())
{
arcT *arc = itr.next();
if (!fixed.containsKey(arc->finish->name))
{
Vector<arcT *> newPath = path;
newPath.add(arc);
queue.enqueue(newPath);
}
}
}
if (queue.isEmpty()) return Vector<arcT *>(); //没有路径
path = queue.dequeueMax();
start = path[path.size() - 1]->finish;
}
return path;
}
nodeT * GetCities(Graph &graph)
{
while(true)
{
string name = GetLine();
Set<nodeT *>::Iterator itrCityA = graph.itrNodes();
while(itrCityA.hasNext())
{
nodeT *node = itrCityA.next();
if (node->name == name)
{
return node;
}
}
}
}
void minPath(Graph &graph)
{
cout << "Choose starting city: ";
nodeT *start = GetCities(graph);
cout <<"The starting city is : "<<start->name << endl;
nodeT *end;
while(true)
{
cout << "Choose destination city: ";
end = GetCities(graph);
if (end->name != start->name)
{
cout <<"The destination city is : "<< end->name << endl;
break;
}
cout << endl << "Please choose a different city." << endl;
}
double cost = 0;
Vector<arcT *> path = FindShortestPath(start,end); //找出最短路径,用vector存放
cout <<"------------------------------------"<<endl;
cout <<"The shortest path is : "<<endl;
for (int i = 0; i < path.size(); i++)
{
cost += path[i]->cost;
cout <<"( "<<path[i]->start->name << " -> " << path[i]->finish->name<<" )"<< endl;
}
cout << "Total Cost = " << cost << endl;
cout << "Total paths = " << path.size() << endl;
cout <<"------------------------------------"<<endl;
}
int arcCostCmp(arcT *a, arcT *b)
{
double aCost = a->cost;
double bCost = b->cost;
if(aCost > bCost) return -1;
if(bCost > aCost) return 1;
return 0;
}
Set<arcT *> kruskal(Graph &graph)
{
PQueue<arcT *> path(arcCostCmp);
Vector< Set<string> > nodes; //每个坑存放一个集合
Set<arcT *>minTree;
// 把弧全部加入PQueue中,并把每个节点单独作一个集合,录入nodes中
Set<arcT *>::Iterator itrArcSet = graph.itrArcs();
while(itrArcSet.hasNext())
{
arcT *arc = itrArcSet.next();
path.enqueue(arc);
bool inAlready = false;
for (int i = 0; i < nodes.size(); i++)
{
if (nodes[i].contains(arc->start->name))
{
inAlready = true;
break;
}
}
if (!inAlready)
{
Set<string> newNode;
newNode.add(arc->start->name);
nodes.add(newNode);
}
}
while (!path.isEmpty())
{
arcT * arc = path.dequeueMax();
// 找出最短弧的开始点和结束的所在的集合
int startN, endN;
startN = endN = -1;
for (int i =0; i < nodes.size(); i++)
{
if (nodes[i].contains(arc->start->name))
startN = i;
if (nodes[i].contains(arc->finish->name))
endN = i;
}
// 如果不在同一个集合中,则把弧加入minTree中,并把开始点和结束的所在的集合合并
if (startN != endN)
{
nodes[startN].unionWith(nodes[endN]);
nodes.removeAt(endN);
minTree.add(arc);
}
}
return minTree;
}
void printminTree(Set<arcT *> s)
{
cout <<"------------------------------------"<<endl;
cout<<"The minTree is : "<<endl;
int count = 0;
Set<arcT *>::Iterator itr = s.iterator();
while(itr.hasNext())
{
arcT *next = itr.next();
cout <<"( "<<next->start->name << " -> " << next->finish->name<<" )"<< endl;
count += next->cost;
}
cout<< "The costs are :"<<count<<endl;
cout <<"------------------------------------"<<endl;
}
void Welcome() {
cout << "Welcome to my Game : pathfinder ! "<< endl;
cout << "Hit return when you're ready...";
GetLine();
cout << endl;
}
int main()
{
Welcome();
Graph graph;
Set<arcT *>minTree;
while (true)
{
int selecton = menu();
switch (selecton)
{
case 1:
cout << endl;
graph.clear();
loadGraphFile(graph);
graph.print();
break;
case 2:
cout <<endl;
minPath(graph);
cout << "Press Enter to continue..."<<endl;
GetLine();
break;
case 3:
minTree = kruskal(graph);
printminTree(minTree);
cout << "Press Enter to continue..."<<endl;
GetLine();
break;
case 4:
exit(0);
default:
exit(0);
}
}
}
五. 测试结果
Welcome to my Game : pathfinder !
Hit return when you're ready...
Your options are:
(1) Choose a new graph file
(2) Find shortest path using Dijkstra's algorithm
(3) Compute the minimal spanning tree using Kruskal's algorithm
(4) Quit
Enter Selection: 1
Enter name of graph data file: USA.txt
SanFrancisco x=0.28 y=2.31 -> LosAngeles, Portland, LasVegas, SaltLakeCity, Denver, Chicago, Minneapolis, WashingtonDC, NewYork,
LosAngeles x=0.62 y=1.6 -> SanFrancisco, LasVegas, Phoenix, Denver, WashingtonDC, NewYork,
Orlando x=5.4 y=0.5 -> Atlanta,
WashingtonDC x=5.71 y=2.25 -> NewYork, Raleigh, SanFrancisco, LosAngeles, Chicago,
NewYork x=5.94 y=2.71 -> Boston, WashingtonDC, SanFrancisco, LosAngeles, Chicago, Minneapolis,
Dallas x=3.31 y=1.04 -> NewOrleans, OklahomaCity, Phoenix, Atlanta,
Portland x=0.46 y=3.17 -> SanFrancisco, Seattle, SaltLakeCity,
Minneapolis x=3.72 y=3.01 -> Chicago, SanFrancisco, NewYork, Seattle, KansasCity,
OklahomaCity x=3.18 y=1.57 -> Dallas, KansasCity, Phoenix, Denver,
Raleigh x=5.67 y=1.74 -> WashingtonDC, Atlanta,
NewOrleans x=4.1 y=0.74 -> Dallas, Atlanta, KansasCity,
Denver x=2.39 y=2.18 -> SanFrancisco, LosAngeles, KansasCity, Chicago, Seattle, OklahomaCity, SaltLakeCity, LasVegas,
SaltLakeCity x=1.58 y=2.5 -> SanFrancisco, Denver, Portland,
Seattle x=0.68 y=3.71 -> Portland, Minneapolis, Denver, Atlanta,
Chicago x=4.42 y=2.49 -> Minneapolis, SanFrancisco, Denver, WashingtonDC, NewYork, Atlanta,
Atlanta x=4.93 y=1.28 -> Seattle, Orlando, Raleigh, NewOrleans, Chicago, Dallas,
Boston x=6.22 y=2.9 -> NewYork,
Phoenix x=1.47 y=1.39 -> LasVegas, LosAngeles, Dallas, OklahomaCity,
LasVegas x=1.11 y=1.85 -> SanFrancisco, LosAngeles, Phoenix, Denver,
KansasCity x=3.56 y=2.08 -> OklahomaCity, Denver, Minneapolis, NewOrleans,
Your options are:
(1) Choose a new graph file
(2) Find shortest path using Dijkstra's algorithm
(3) Compute the minimal spanning tree using Kruskal's algorithm
(4) Quit
Enter Selection: 2
Choose starting city: Dallas
The starting city is : Dallas
Choose destination city: LasVegas
The destination city is : LasVegas
------------------------------------
The shortest path is :
( Dallas -> Phoenix )
( Phoenix -> LasVegas )
Total Cost = 980
Total paths = 2
------------------------------------
Press Enter to continue...
Your options are:
(1) Choose a new graph file
(2) Find shortest path using Dijkstra's algorithm
(3) Compute the minimal spanning tree using Kruskal's algorithm
(4) Quit
Enter Selection: 3
------------------------------------
The minTree is :
( SanFrancisco -> LosAngeles )
( Portland -> SanFrancisco )
( Portland -> Seattle )
( Boston -> NewYork )
( NewOrleans -> Dallas )
( LosAngeles -> LasVegas )
( NewYork -> WashingtonDC )
( Minneapolis -> Chicago )
( OklahomaCity -> Dallas )
( OklahomaCity -> KansasCity )
( LasVegas -> Phoenix )
( Raleigh -> WashingtonDC )
( Atlanta -> Orlando )
( Atlanta -> Raleigh )
( Atlanta -> NewOrleans )
( Denver -> OklahomaCity )
( SaltLakeCity -> Denver )
( SaltLakeCity -> Portland )
( Minneapolis -> KansasCity )
The costs are :5820
------------------------------------
Press Enter to continue...