首页 > 代码库 > 通信网Project之——单源单宿最短路问题
通信网Project之——单源单宿最短路问题
最基本的Vertex类:
#ifndef VERTEX_H #define VERTEX_H #include <climits> #include <cstddef> #define INF INT_MAX class 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
最后是运行结果了!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。