最短路径--狄克斯特拉（Dijkstra）算法

最短路径

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径                            

                                        

Dijkstra算法

算法来源

Dijkstra算法是由一个叫Dijkstra的荷兰人发明的，故称此算法为Dijkstra算法

 

算法思想

• 将图上的初始点看作一个集合S，其它点看作另一个集合
• 根据初始点，求出其它点到初始点的距离d[i] （若相邻，则d[i]为边权值；若不相邻，则d[i]为无限大）
• 选取最小的d[i]（记为d[x]），并将此d[i]边对应的点（记为x）加入集合S（实际上，加入集合的这个点的d[x]值就是它到初始点的最短距离）
• 再根据x，更新跟 x 相邻点 y 的d[y]值：d[y] = min{ d[y], d[x] + 边权值w[x][y] }，因为可能把距离调小，所以这个更新操作叫做松弛操作。
• 重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d[i]即为最短路径长度。

 

算法缺陷

只能处理有向无环，且权重为正的图

 

代码实现

/*! *@file Dijkstra.h *@brief 狄克斯特拉算法,适用于有向无环图，且权重非负 */#ifndef DIJKSTRA_H #define DIJKSTRA_H#include <iostream> #include <string> #include <set> #include <list> #include <map>const double g_Infinity = 1E100;struct CNode;struct CEdge {CNode* m_neighborNode;double m_dist;CEdge(CNode* pNeighborNode, double dist) : m_neighborNode(pNeighborNode), m_dist(dist) {}~CEdge() {} };struct CNode {std::string m_name;std::set<CEdge*> m_edges;CNode(std::string name) : m_name(name) {}~CNode() {for (auto iter = m_edges.begin(); iter != m_edges.end(); ++iter){delete* iter;}m_edges.clear();}void AddEdge(CNode* pNode, double dist){m_edges.insert(new CEdge(pNode, dist));}void AddEdge(CEdge* pEdge){m_edges.insert(pEdge);}bool operator<(const CNode& node) const{return this->m_name.compare(node.m_name) < 0;} };class CGraph { public:CGraph() {}~CGraph() {}bool Dijkstra(CNode* pNodeStart, CNode* pNodeEnd, std::list<CNode*>& path, double& dist){if (!pNodeStart || !pNodeEnd)return false;Init(pNodeStart);bool bSuc(false);CNode* pNodeLowest = FindLowestNode(dist);while (pNodeLowest){if (pNodeLowest == pNodeEnd){bSuc = true;break;}std::set<CEdge*> edges = pNodeLowest->m_edges;for (auto iter = edges.begin(); iter != edges.end(); ++iter){double dCostNew = dist + (*iter)->m_dist;UpdateCostMap((*iter)->m_neighborNode, pNodeLowest, dCostNew);}m_processedNodes.insert(pNodeLowest);pNodeLowest = FindLowestNode(dist);}if (bSuc){bSuc = CreatePath(pNodeLowest, pNodeStart, path);}return bSuc;} private:void Init(CNode* pNodeStart){m_costMap.clear();m_processedNodes.clear();std::set<CEdge*> edges = pNodeStart->m_edges;for (auto iter = edges.begin(); iter != edges.end(); ++iter){CNode* pNode = (*iter)->m_neighborNode;double dCost = (*iter)->m_dist;m_costMap.insert(std::make_pair(pNode, std::make_pair(pNodeStart, dCost)));}}void UpdateCostMap(CNode* pNode, CNode* pParentNode, double cost){auto iter = m_costMap.find(pNode);if (iter != m_costMap.cend()){double oldCost = iter->second.second;if (oldCost > cost){m_costMap[pNode] = std::make_pair(pParentNode, cost);}}else{m_costMap.insert(std::make_pair(pNode, std::make_pair(pParentNode, cost)));}}CNode* FindLowestNode(double& dist){dist = g_Infinity;CNode* pResult(nullptr);for (auto iter = m_costMap.begin(); iter != m_costMap.end(); ++iter){CNode* pNode = iter->first;double distNode = iter->second.second;if (distNode < dist && m_processedNodes.find(pNode) == m_processedNodes.end()){pResult = pNode;dist = distNode;}}return pResult;}bool CreatePath(CNode* pNode, CNode* pStartNode, std::list<CNode*>& path){path.push_front(pNode);while (pNode != pStartNode){if (!pNode){path.clear();return false;}auto iter = m_costMap.find(pNode);if (iter == m_costMap.end()){path.clear();return false;}pNode = iter->second.first;path.push_front(pNode);}return true;}private:std::map<CNode*, std::pair<CNode*, double>> m_costMap;std::set<CNode*> m_processedNodes; };void Print(const std::list<CNode*>& path) {std::cout << "path: ";for (auto iter = path.begin(); iter != path.end(); ++iter){std::cout << " --> " << (*iter)->m_name;}//std::cout << std::endl; }void DijkstraTest() {CNode* pNodeS = new CNode("start");CNode* pNodeF = new CNode("end");CNode* pNodeA = new CNode("A");CNode* pNodeB = new CNode("B");pNodeS->AddEdge(pNodeA, 6);pNodeS->AddEdge(pNodeB, 2);pNodeB->AddEdge(pNodeA, 3);pNodeB->AddEdge(pNodeF, 5);pNodeA->AddEdge(pNodeF, 1);CGraph cg;std::list<CNode*> path;double dist = g_Infinity;bool bSuc = cg.Dijkstra(pNodeS, pNodeF, path, dist);if (bSuc){Print(path);std::cout << " dist: " << dist << std::endl;}else{std::cout << "failed!!!" << std::endl;}delete pNodeS;delete pNodeF;delete pNodeA;delete pNodeB;pNodeS = nullptr;pNodeF = nullptr;pNodeA = nullptr;pNodeB = nullptr; }#endif // !DIJKSTRA_H

总结

以上是生活随笔为你收集整理的最短路径--狄克斯特拉（Dijkstra）算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。