1 有向加权图的数据结构如下
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
2 实现的C++代码如下,可以由其中的某个顶点起,找到可达的所有最短路径
Graph.h头文件,描述了加权有向边,加权有向图,和最短路径算法
/* * Graph.h * * Created on: 2014年5月17日 * Author: zhongchao */ #ifndef _GRAPH_ #define _GRAPH_ #include <fstream> #include <iostream> #include <ext/hash_map> #include <hash_set> #include <map> #include<limits> #include <stdio.h> #include <string.h> using namespace std; using namespace __gnu_cxx; /* * 有向图算法:最短路径 */ //----------------------带权重的有向边-------------------- class DirWeightEdge { private: int _from; //起点 int _to; //终点 double _weight; //权重 public: DirWeightEdge(); DirWeightEdge(int a, int b, double c); ~DirWeightEdge(); int from(); int to(); double weight(); }; //--------------------------------------------------------------------- //---------------------带权重的有向图---------------------- class DirWeightGraph { private: hash_map<int, vector<DirWeightEdge*> > adj; //邻接表 hash_set<int> nodes; int _eNum; //边的个数 int _vNum; //节点个数 public: DirWeightGraph(string path); ~DirWeightGraph(); void addEdge(int f, int t, double w); vector<DirWeightEdge*> getAdj(int n); int e(); int v(); vector<DirWeightEdge*> edges(int node); hash_set<int> getNodes(); }; //--------------------------------最短路径算法----------------------------- class Dijkstra { private: bool* mark; //标记被访问过的节点 double* distTo; //从起点开始到某个终点的距离 DirWeightEdge** edgeTo; //存储最短路径的中的边 map<double, int> pq; hash_set<int> pqMark; int startNode; int nodeNum; public: Dijkstra(DirWeightGraph* graph, int node); ~Dijkstra(); void visit(DirWeightGraph* graph, int v); bool hasPathTo(int n); vector<DirWeightEdge*> pathTo(int n); void allPath(DirWeightGraph* graph, int n); void printPath(vector<DirWeightEdge*> & path); }; //---------------------------------------------------------------------- #endif /* _GRAPH_*/
头文件Graph.h对应的源文件实现
/* * Graph.cpp * * Created on: 2014年5月17日 * Author: zhongchao */ #include "Graph.h" DirWeightEdge::DirWeightEdge(int a, int b, double c) { this->_from = a; this->_to = b; this->_weight = c; } DirWeightEdge:: ~DirWeightEdge() { } int DirWeightEdge::from() { return _from; } int DirWeightEdge::to() { return _to; } double DirWeightEdge::weight() { return _weight; } //---------------------------------有向图--------------------------------- hash_set<int> DirWeightGraph::getNodes() { return nodes; } void DirWeightGraph::addEdge(int f, int t, double w) { DirWeightEdge* dirWeightEdge = new DirWeightEdge(f, t, w); if(adj.find(f) != adj.end()) { adj.find(f)->second.push_back(dirWeightEdge); } else { vector<DirWeightEdge*> edges; edges.push_back(dirWeightEdge); adj.insert(pair<int, vector<DirWeightEdge*> >(f, edges)); } } DirWeightGraph::DirWeightGraph(string path) { this->_eNum = 0; this->_vNum = 0; ifstream reader(path.c_str(), ios_base::in); if(reader.is_open()) { while(!reader.eof()) { int f, t; double w; reader>>f>>t>>w; if(reader.fail()) break; //cout<<f<<" "<<t<<" "<<w<<endl; nodes.insert(f); nodes.insert(t); addEdge(f, t, w); _eNum++; //边的条数 } } } int DirWeightGraph::e() { return _eNum; } int DirWeightGraph::v() { return nodes.size(); } vector<DirWeightEdge*> DirWeightGraph::getAdj(int n) { return adj.find(n)->second; } DirWeightGraph::~DirWeightGraph() { for(hash_map<int, vector<DirWeightEdge*> >::iterator it = adj.begin(); it != adj.end(); it++) { for(vector<DirWeightEdge*>::iterator it1 = it->second.begin(); it1 != it->second.end(); it1++) { delete *it1; } } } //Dijkstra最短路径算法 Dijkstra::Dijkstra(DirWeightGraph* graph, int v) { mark = new bool[graph->v()]; distTo = new double[graph->v()]; edgeTo = new DirWeightEdge* [graph->v()]; startNode = v; nodeNum = graph->v(); //edgeTo = new vector<DirWeightEdge*>(); //pq = new map<double, int>(); for(int i = 0; i < graph->v(); i++) { distTo[i] = numeric_limits<double>::max(); //无穷大 mark[i] = false; } distTo[v] = 0.0; mark[v] = true; pq.insert(pair<double, int>(0.0, v)); pqMark.insert(0); while(pq.size() != 0) { int v = pq.begin()->second; pq.erase(pq.begin()); visit(graph, v); } } void Dijkstra::visit(DirWeightGraph* graph, int v) { vector<DirWeightEdge*> edges = graph->getAdj(v); for(vector<DirWeightEdge*>::iterator it = edges.begin(); it != edges.end(); it++) { int f = (*it)->from(); int t = (*it)->to(); double w = (*it)->weight(); if(distTo[t] > distTo[f] + w) { mark[t] =true; distTo[t] = distTo[f] + w; edgeTo[t] = *it; if(pqMark.find(t) == pqMark.end()) { pq.insert(pair<double, int>( distTo[t], t)); pqMark.insert(t); } else { edgeTo[t] = *it; for(map<double, int>::iterator it = pq.begin(); it != pq.end(); it++) { if(it->second == t) { pq.erase(it); pq.insert(pair<double, int>(distTo[t], t )); } } } } } } bool Dijkstra::hasPathTo(int n) { return mark[n]; } vector<DirWeightEdge*> Dijkstra::pathTo(int n) { vector<DirWeightEdge*> paths; if(hasPathTo(n)) { DirWeightEdge* e = edgeTo[n]; int f = e->from(); paths.push_back(e); while(f != startNode) { e = edgeTo[f]; f = e->from(); paths.push_back(e); } } return paths; } void Dijkstra::printPath(vector<DirWeightEdge*>& path) { vector<DirWeightEdge*>::reverse_iterator rit; for(rit = path.rbegin(); rit != path.rend(); rit++) { cout<<(*rit)->from()<<"->"; } cout<<(*path.begin())->to(); } void Dijkstra::allPath(DirWeightGraph* graph, int node) { hash_set<int> nodes = graph->getNodes(); for(hash_set<int>::iterator it = nodes.begin(); it != nodes.end(); it++) { int n = *it; if (n == node) continue; if(hasPathTo(n)) { vector<DirWeightEdge*> paths = pathTo(n); printPath(paths); cout<<": weight=" <<distTo[n]<<endl; } } } Dijkstra::~Dijkstra() { delete[] mark; delete[] distTo; for(int i = 0; i < nodeNum; i++) { delete edgeTo[i]; } delete[] edgeTo; }
测试程序如下
#include "Graph.h" int main(int argc, char** argv) { //最短路径算法 string path("tinyEWD.txt"); //<span style="font-family: Arial, Helvetica, sans-serif;">tinyEWD.txt 存储图的文件</span> DirWeightGraph* dirWeightGraph = new DirWeightGraph(path); //实例化有向加权图对象 int n = 1; //最短路径的起点 Dijkstra* dijkstra = new Dijkstra(dirWeightGraph, n); //实例化最短路径对象 dijkstra->allPath(dirWeightGraph, n); //打印可达点的路径 return 1; }
从起点1开始的所有可达点的最短路径如下
1->3->6->0: weight=1.39
1->3->6->2: weight=1.21
1->3: weight=0.29
1->3->6->4: weight=1.74
1->3->6->2->7->5: weight=1.83
1->3->6: weight=0.81
1->3->6->2->7: weight=1.55