C++實現Dijkstra算法的示例代碼
一、算法原理
鏈接: 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算法的資料請關註WalkonNet其它相關文章!