最主要的Vertex类：
#ifndef VERTEX_H
#define VERTEX_H#include <climits>
#include <cstddef>
#define INF INT_MAXclass Vertex
{
public:
int ID;
Vertex* parent;
int d;Vertex(int id) : ID(id), d(INF), parent(NULL){}
};#endif
接下来是Edge类：
#ifndef EDGE_H
#define EDGE_H#include "vertex.h"class Edge
{
private:
float weight;
float capacity;
float passrate;public:
int id;
Vertex* tail;
Vertex* head;
/******** constructor *******/
Edge(int ID, Vertex& t, Vertex& h, float wght = 1,
float cap = 1, float pssrt = 1) :
id(ID), head(&h), tail(&t), weight(wght),
capacity(cap), passrate(pssrt) {}/********** The ID **********/
void setId(int ID)
{
id = ID;
}
int getId()
{
return id;
}/********* The vertex ********/
void setTail(Vertex& v)
{
tail = &v;
}
void setHead(Vertex& v)
{
head = &v;
}/******** Other method *******/
void setWeight(const float w)
{
weight = w;
}
float getWeight()
{
return weight;
}
float getCapacity()
{
return capacity;
}
float getPassRate()
{
return passrate;
}};#endif
当然还有路问题须要的Path类：
#ifndef PATH_H
#define PATH_H#include <list>
#include "vertex.h"class Path : std::list<Vertex*>
{
public:
Path(Vertex& tail);void print();
};#endif
这是Path类的实现：
#include "path.h"
#include <iostream>
#include "vertex.h"
#include <list>using namespace std;Path::Path(Vertex& tail)
{
Vertex* temp = &tail;
while (temp->parent != NULL)
{
push_back(temp);
temp = temp->parent;
}
push_back(temp);
}void Path::print()
{
reverse();
list<Vertex*>::iterator it;
it = begin();
cout << "Vertex " << (*it)->ID;
it++;
for (; it != end(); it++)
cout << " -> Vertex " << (*it)->ID;
}
下来就是最重要也是最复杂的Graph类了！
#ifndef GRAPH_H
#define GRAPH_H#include <map>
#include "edge.h"
#include "vertex.h"
#include "path.h"
#include <set>
#include <list>class Graph
{
std::map<int, Vertex*> vertexMap;
// The map: vertex and its incident edge.
std::map<Vertex*, std::list<Edge*> > incMap;
std::set<Edge*> edgeList;
std::list<Vertex*> notMarkedVertex;
bool fromFile;
Path* path;void update(Vertex* v);public:
/********** constructor *********/
Graph(): fromFile(false){}
Graph(const char* inputFileName);
Graph(std::list<Edge*>& edge);
~Graph();/*********** size info **********/
int getNumVertex()
{
return vertexMap.size();
}
int getNumEdge()
{
return edgeList.size();
}void print();
void addEdge(Edge& edge);
void dijkstra(int s, int d);
void dijkstra(Vertex& s, Vertex& d);
};#endif
下来是实现：
#include "graph.h"
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <list>
#include <string>
#include <cstdlib>using namespace std;Graph::Graph(const char* inputFileName)
{
fromFile = true;
ifstream in(inputFileName);string s;
getline(in, s);
getline(in, s);while (in.good())
{
int id, tail, head;
float weight, capacity, passrate;
in >> id >> tail >> head
>> weight >> capacity >> passrate;
map<int, Vertex*>::iterator it;
it = vertexMap.find(tail);Vertex *t;
Vertex *h;if (it == vertexMap.end())
t = new Vertex(tail);
else
t = it->second;it = vertexMap.find(head);
if (it == vertexMap.end())
h = new Vertex(head);
else
h = it->second;Edge* e = new Edge(id, *t, *h, weight, capacity, passrate);
addEdge(*e);
}
}Graph::Graph(list<Edge*>& edge)
{
list<Edge*>::iterator it;
for (it = edge.begin(); it != edge.end(); it++)
addEdge(**it);
fromFile = false;
}void Graph::addEdge(Edge& edge)
{
edgeList.insert(&edge);
vertexMap.insert(pair<int, Vertex*>(edge.tail->ID, edge.tail));
vertexMap.insert(pair<int, Vertex*>(edge.head->ID, edge.head));if (incMap.find(edge.tail) == incMap.end())
{
list<Edge*>* l = new list<Edge*>(1, &edge);
incMap.insert(pair<Vertex*, list<Edge*> >(edge.tail, *l));
}
else
incMap.find(edge.tail)->second.push_back(&edge);
}void Graph::print()
{
map<Vertex*, list<Edge*> >::iterator it;
list<Edge*>::iterator it2;
for (it = incMap.begin(); it != incMap.end(); it++)
{
cout << "Vertex " << it->first->ID << endl;
for (it2 = it->second.begin();
it2 != it->second.end();
it2++)
cout << "\tEdge " << (*it2)->id << " to Vertex "
<< (*it2)->head->ID << endl;
}
}Graph::~Graph()
{
if (fromFile)
{
set<Edge*>::iterator it;
for (it = edgeList.begin();
it != edgeList.end();
it++)
delete *it;map<int, Vertex*>::iterator it2;
for (it2 = vertexMap.begin();
it2 != vertexMap.end();
it2++)
delete it2->second;
}
}bool comp(Vertex* a, Vertex* b)
{
return a->d < b->d;
}void Graph::update(Vertex* v)
{
list<Edge*> inc = incMap[v];
if (inc.size() == 0)
{
cerr << "No out degree!" << endl;
exit(EXIT_FAILURE);
}list<Edge*>::iterator it;
for (it = inc.begin(); it != inc.end(); it++)
{
int d = v->d + (*it)->getWeight();
if ((*it)->head->d > d)
{
(*it)->head->parent = v;
(*it)->head->d = d;
}
}
}void Graph::dijkstra(int sid, int did)
{
Vertex* s = vertexMap[sid];
Vertex* temp;
s->d = 0;map<int, Vertex*>::iterator it;
for (it = vertexMap.begin();
it != vertexMap.end();
it++)
if (it->second->ID != sid)
notMarkedVertex.push_back(it->second);
update(s);do
{
notMarkedVertex.sort(comp);
temp = notMarkedVertex.front();
notMarkedVertex.pop_front();
if (temp->ID == did)
break;
update(temp);
}while(!notMarkedVertex.empty());path = new Path(*vertexMap[did]);
path->print();
}void Graph::dijkstra(Vertex& s, Vertex& d)
{
dijkstra(s.ID, d.ID);
}
眼下的工作就是这些了。
以下是一个測试程序：
test.cpp:
#include <iostream>
#include "graph.h"
#include "path.h"using namespace std;int main()
{
Graph graph("InputFile.txt");
graph.print();cout << "Please input the s and d: ";
int s, d;
cin >> s >> d;
graph.dijkstra(s, d);return 0;
}
还有InputFile.txt 的内容：
n 7
e 9
1 1 2 1 20 0.8
2 2 3 5 30 0.8
3 3 6 6 22 0.6
4 7 6 5 22 0.4
5 1 7 3 20 0.2
6 5 6 2 20 0.3
7 3 5 1 20 0.5
8 4 5 6 20 0.6
9 2 4 2 20 0.7
最后是执行结果了！
