C++实现Dijkstra算法的示例代码

目录

一、算法原理

二、具体代码

1.graph类

2.PathFinder类

3. main.cpp

三、示例

一、算法原理

链接: Dijkstra算法及其C++实现参考这篇文章

二、具体代码 1.graph类

graph类用于邻接表建立和保存有向图。

graph.h:

#ifndef GRAPH_H #define GRAPH_H #include <iostream> #include <string> #include <vector> #include <stdlib.h> using namespace std; // 定义顶点 typedef struct EdgeNode { int adjvex;// 顶点下标 struct EdgeNode *next;// 下一条边的指针 double cost;// 当前边的代价 EdgeNode(); ~EdgeNode(); } EdgeNode; // 定义顶点表 typedef struct VexList { string Vexs; //用来存储顶点信息 EdgeNode *firstedge; //用来存储当前顶点的下一个顶点 VexList(); ~VexList(); } VertexList; // 定义图 typedef class GraphList { public: GraphList(); ~GraphList(); void PrintGraph();// 打印图 void CreateGraph();// 构建图 vector<VexList> VexList; int Vertexs, Edges; } GraphList; typedef GraphList* GraphListPtr; #endif

graph.cpp

#include <graph.h> EdgeNode::EdgeNode() { cost = 0; next = nullptr; } EdgeNode::~EdgeNode() { //cout << "delete Node" << endl; } VexList::VexList() { firstedge = nullptr; } VexList::~VexList() { //cout << "delete VexList" << endl; } GraphList::GraphList() { VexList.clear(); } GraphList::~GraphList() { //cout << "delete GraphList" << endl; } void GraphList::PrintGraph() { cout << "所建立的地图如以下所示:" << endl; for (int i = 0; i< Vertexs; i++) { cout << VexList[i].Vexs; //先输出顶点信息 EdgeNode * e = VexList[i].firstedge; while (e) { //然后就开始遍历输出每个边表所存储的邻接点的下标 if (e->cost == -1) { cout << "---->" << e->adjvex; } else { cout << "-- " << e->cost << " -->" << e->adjvex; } e = e->next; } cout << endl; } } void GraphList::CreateGraph() { EdgeNode *e = new EdgeNode(); cout << "请输入顶点数和边数:" << endl; cin >> Vertexs >> Edges; cout << "请输入顶点的信息:" << endl; for (int i = 0; i <Vertexs; ++i) { VertexList tmp; cin >> tmp.Vexs; tmp.firstedge = NULL; VexList.push_back(tmp); } for (int k = 0; k < Edges; ++k) { int i, j;//(Vi,Vj) double cost; cout << "请输入边(Vi,Vj)与 cost:" << endl; cin >> i >> j >> cost; if (VexList[i].firstedge == NULL) {//当前顶点i后面没有顶点 e = new EdgeNode; e->adjvex = j; e->cost = cost; e->next = NULL; VexList[i].firstedge = e; } else { //当前i后面有顶点 EdgeNode *p = VexList[i].firstedge; while (p->next) { p = p->next; } e = new EdgeNode; e->adjvex = j; e->cost = cost; e->next = NULL; p->next = e; } } } 2.PathFinder类

PathFinder类用于搜索最短路径

pathFinder.h

#ifndef PATH_FINDER_H #define PATH_FINDER_H #include <iostream> #include <graph.h> #include <queue> enum State{OPEN = 0, CLOSED, UNFIND}; // 定义dijkstra求解器 class DijNode { public: DijNode(); DijNode(double _val); ~DijNode() {}; double getCost() { return m_cost; } State getState() { return m_state; } void setCost(double _val) { m_cost = _val; } void setState(State _state) { m_state = _state; } int getIndex() { return m_index; } void setIndex(int _idx) { m_index = _idx; } void setPred(DijNode* _ptr) { preNode = _ptr; } DijNode* getPred() { return preNode; } VertexList Vertex; private: int m_index; double m_cost;// 起点到当前点的代价 State m_state; DijNode* preNode;// 保存父节点 }; typedef DijNode* DijNodePtr; // 构造优先队列用的 struct cmp { bool operator() (DijNodePtr &a, DijNodePtr &b) { return a->getCost() > b->getCost(); } }; class PathFinder { public: priority_queue<DijNodePtr, vector<DijNodePtr>, cmp > openList;//用优先队列做openList,队首元素为最小值 vector<DijNodePtr> m_path;// 存放最终路径 PathFinder() { openList.empty(); m_path.clear(); } ~PathFinder() {}; void StoreGraph(GraphListPtr _graph); void Search(int start, int end); void retrievePath(DijNodePtr _ptr); vector<DijNodePtr> NodeList; private: GraphListPtr m_graph; /*vector<DijNodePtr> NodeList;*/ }; typedef PathFinder* PathFinderPtr; #endif

PathFinder.cpp

#include <PathFinder.h> DijNode::DijNode() { m_cost = -1;// -1表示未被探索过,距离为无穷,非负数表示已经被探索过 m_index = -1; m_state = UNFIND;// OPEN表示openlist, CLOSED表示在closeList中,UNFIND表示未探索过 preNode = nullptr; } DijNode::DijNode(double _val) { m_cost = _val;// -1表示未被探索过,非负数表示已经被探索过 m_index = -1; m_state = UNFIND;// OPEN表示openlist, CLOSED表示在closeList中,UNFIND表示未探索过 preNode = nullptr; } void PathFinder::StoreGraph(GraphListPtr _graph) { for (int i = 0; i < _graph->VexList.size(); ++i) { DijNodePtr node = new DijNode(); node->Vertex = _graph->VexList[i]; node->setIndex(i); NodeList.push_back(node); } } void PathFinder::Search(int start, int end) { // 搜索起点 DijNodePtr m_start = NodeList[start]; m_start->setCost(0); m_start->setIndex(start); m_start->setState(OPEN); openList.push(m_start); int count = 0; while (!openList.empty()) { // 弹出openList中的队首元素 DijNodePtr cur = openList.top(); cur->setState(CLOSED);// 加入closelist中 openList.pop(); // 遍历队首元素所有的边 EdgeNode *e = cur->Vertex.firstedge; while (e != nullptr) { int _index = e->adjvex; double _cost = e->cost; //cout << "_cost = " << _cost << endl; // 如果节点在close list中,直接跳过 if (NodeList[_index]->getState() == CLOSED) { continue; } if (NodeList[_index]->getCost() == -1) { NodeList[_index]->setCost(cur->getCost() + _cost);// 更新代价 NodeList[_index]->setPred(cur);// 更新父节点 NodeList[_index]->setState(OPEN);// 加入open list中 openList.push(NodeList[_index]); } else if (cur->getCost() + _cost < NodeList[_index]->getCost()) { // 如果从当前节点到第_index个节点的距离更短,更新距离和父节点 NodeList[_index]->setCost(cur->getCost() + _cost);// 更新代价 NodeList[_index]->setPred(cur);// 更新父节点 NodeList[_index]->setState(OPEN);// 加入open list中 } e = e->next; } } cout << "最短距离为:" << NodeList[end]->getCost() << endl; retrievePath(NodeList[end]); } void PathFinder::retrievePath(DijNodePtr ptr) { while (ptr != nullptr) { m_path.push_back(ptr); ptr = ptr->getPred(); } reverse(m_path.begin(),m_path.end()); } 3. main.cpp

主函数

#include <graph.h> #include <PathFinder.h> int main() { cout << "构建地图" << endl; GraphListPtr graph = new GraphList(); graph->CreateGraph(); cout << "\n \n"; graph->PrintGraph(); PathFinderPtr _solver = new PathFinder(); _solver->StoreGraph(graph); cout << "\n \n"; int start, end; cout << "输入起点" << endl; cin >> start; cout << "输入终点" << endl; cin >> end; cout << "\n \n"; _solver->Search(start, end); cout << "最短路径为:"; for (int i = 0; i < _solver->m_path.size(); ++i) { cout << _solver->m_path[i]->Vertex.Vexs ; if (i < _solver->m_path.size() - 1) cout << "-->"; } cout << endl; system("pause"); return 0; } 三、示例

以上就是C++实现Dijkstra算法的示例代码的详细内容,更多关于C++ Dijkstra算法的资料请关注易知道(ezd.cc)其它相关文章!

推荐阅读