怎么使用C++实现Dijkstra算法

本篇内容介绍了“怎么使用C++实现Dijkstra算法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

具体代码

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;};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算法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！