最短路徑

從圖中的某個(gè)頂點(diǎn)出發(fā)到達(dá)另外一個(gè)頂點(diǎn)的所經(jīng)過(guò)的邊的權(quán)重和最小的一條路徑，稱(chēng)為最短路徑? ? ? ? ? ? ? ? ? ? ? ? ? ??

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Dijkstra算法

算法來(lái)源

Dijkstra算法是由一個(gè)叫Dijkstra的荷蘭人發(fā)明的，故稱(chēng)此算法為Dijkstra算法

?

算法思想

• 將圖上的初始點(diǎn)看作一個(gè)集合S，其它點(diǎn)看作另一個(gè)集合
• 根據(jù)初始點(diǎn)，求出其它點(diǎn)到初始點(diǎn)的距離d[i] （若相鄰，則d[i]為邊權(quán)值；若不相鄰，則d[i]為無(wú)限大）
• 選取最小的d[i]（記為d[x]），并將此d[i]邊對(duì)應(yīng)的點(diǎn)（記為x）加入集合S（實(shí)際上，加入集合的這個(gè)點(diǎn)的d[x]值就是它到初始點(diǎn)的最短距離）
• 再根據(jù)x，更新跟 x 相鄰點(diǎn) y 的d[y]值：d[y] = min{ d[y], d[x] + 邊權(quán)值w[x][y] }，因?yàn)榭赡馨丫嚯x調(diào)小，所以這個(gè)更新操作叫做松弛操作。
• 重復(fù)3，4兩步，直到目標(biāo)點(diǎn)也加入了集合，此時(shí)目標(biāo)點(diǎn)所對(duì)應(yīng)的d[i]即為最短路徑長(zhǎng)度。

?

算法缺陷

只能處理有向無(wú)環(huán)，且權(quán)重為正的圖

?

代碼實(shí)現(xiàn)

/*! *@file Dijkstra.h *@brief 狄克斯特拉算法,適用于有向無(wú)環(huán)圖，且權(quán)重非負(fù) */#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

總結(jié)

以上是生活随笔為你收集整理的最短路径--狄克斯特拉（Dijkstra）算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。