下面该代码是对dijkstra算法的实现：
#ifndef __CDIJKSTRA__H #define __CDIJKSTRA__H #include <iostream> #include <string> #include <vector> //dijkstra 算法 仅针无负权有向图 const int NERVER_ATTACH = 9999; struct AdjacencyNode // 邻接点 含加权 { struct VertexNode* pNode; int nWeight; // 加权值 }; struct VertexNode // 顶点 { std::string cName; // 顶点名字 int nInDegree; // 入度 int nDistance; // 最短路径 std::vector<struct AdjacencyNode> vectNodes; // 邻接点 VertexNode() { cName = ""; nInDegree = NERVER_ATTACH; // 未分配的顶点 nDistance = NERVER_ATTACH; vectNodes.clear(); } }; class CDijkstra { public: CDijkstra(int nNodes); ~CDijkstra(); public: bool InsertEdge(std::string aIn, std::string bOut, int nWeight); // 插入有向边 aIn-->aOut 及加权 void Dijkstra(std::string sVertex); // 查找顶点strNode到所有顶点的最短路径 private: void FindIndexInsert(std::string aIn, int& nInsertIndex, bool& bFindInsert, bool& bFindIn); private: struct VertexNode* m_pNodes; // 所有顶点的集合 int m_nNodes; // 顶点数量 }; #endif #include "Dijkstra.h" #include <queue> CDijkstra::CDijkstra(int nNodes) : m_nNodes(nNodes) { m_pNodes = new struct VertexNode[nNodes]; } CDijkstra::~CDijkstra() { delete[] m_pNodes; } void CDijkstra::FindIndexInsert(std::string aIn, int& nInsertIndex, bool& bFindInsert, bool& bFindIn) { nInsertIndex = 0; bFindInsert = false; bFindIn = false; for (int i = 0; i < m_nNodes; i++) { if ((m_pNodes + i)->cName != aIn && (m_pNodes + i)->nInDegree == NERVER_ATTACH && !bFindInsert) { nInsertIndex = i; bFindInsert = true; } if ((m_pNodes + i)->cName == aIn) { bFindIn = true; nInsertIndex = i; break; } } } bool CDijkstra::InsertEdge(std::string aIn, std::string bOut, int nWeight) { int nInsertIndex = 0; bool bFindInsert = false; bool bFindIn = false; int nInsertIndexOut = 0; bool bFindInsertOut = false; bool bFindInOut = false; FindIndexInsert(aIn, nInsertIndex, bFindInsert, bFindIn); if (bFindInsert && !bFindIn) // 还未分配 { (m_pNodes + nInsertIndex)->cName = aIn; (m_pNodes + nInsertIndex)->nInDegree = 0; // 入度为0 } FindIndexInsert(bOut, nInsertIndexOut, bFindInsertOut, bFindInOut); if (bFindInsertOut && !bFindInOut) // 还未分配 { (m_pNodes + nInsertIndexOut)->cName = bOut; (m_pNodes + nInsertIndexOut)->nInDegree = 0; // 入度为0 } (m_pNodes + nInsertIndexOut)->nInDegree += 1; // 入度加1 struct AdjacencyNode objNode; objNode.nWeight = nWeight; objNode.pNode = m_pNodes + nInsertIndexOut; (m_pNodes + nInsertIndex)->vectNodes.push_back(objNode); // 改变邻接表 return true; } void CDijkstra::Dijkstra(std::string sVertex) { int nInsertIndex = 0; bool bFindInsert = false; bool bFindIn = false; FindIndexInsert(sVertex, nInsertIndex, bFindInsert, bFindIn); if (!bFindIn) // 没有该顶点 return; for (int i = 0; i < m_nNodes; i++) // 初始化到所有顶点的路径长度 (m_pNodes + i)->nDistance = NERVER_ATTACH; //unknow (m_pNodes + nInsertIndex)->nDistance = 0; // 自己到自己的路径为0 std::queue<struct VertexNode*> queueNode; queueNode.push(m_pNodes + nInsertIndex); while (!queueNode.empty()) { VertexNode* pNode = queueNode.front(); queueNode.pop(); if (!pNode->vectNodes.empty()) // 是否有邻接点 { for (auto iter = pNode->vectNodes.begin(); iter != pNode->vectNodes.end(); iter++) { if (iter->pNode->nDistance == NERVER_ATTACH) // 更新 { iter->pNode->nDistance = pNode->nDistance + iter->nWeight; queueNode.push(iter->pNode); } else if (iter->nWeight + pNode->nDistance < iter->pNode->nDistance) { iter->pNode->nDistance = iter->nWeight + pNode->nDistance; queueNode.push(iter->pNode); } } } } // 打印最短路径 for (int i = 0; i < m_nNodes; i++) { std::cout << sVertex << " 到顶点" << (m_pNodes + i)->cName << "的最短距离为: "; if ((m_pNodes + i)->nDistance == NERVER_ATTACH) std::cout << "无法到达" << std::endl; else std::cout << (m_pNodes + i)->nDistance << std::endl; } } #include "Dijkstra.h" int main() { CDijkstra objDijstra(7); objDijstra.InsertEdge("v1", "v2", 2); objDijstra.InsertEdge("v1", "v4", 1); objDijstra.InsertEdge("v2", "v4", 3); objDijstra.InsertEdge("v2", "v5", 10); objDijstra.InsertEdge("v3", "v6", 5); objDijstra.InsertEdge("v3", "v1", 4); objDijstra.InsertEdge("v4", "v3", 2); objDijstra.InsertEdge("v4", "v5", 2); objDijstra.InsertEdge("v4", "v6", 8); objDijstra.InsertEdge("v4", "v7", 4); objDijstra.InsertEdge("v5", "v7", 6); objDijstra.InsertEdge("v7", "v6", 1); objDijstra.Dijkstra("v1"); std::cin.get(); return 0; }