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;
}

三、示例