2
我正在學習從一本書尋路，但我發現了一些奇怪的聲明。Dijkstra的尋路算法
爲了完整起見，我將包括大部分的代碼，但隨時可以跳到第二部分（搜索（））
template <class graph_type >
class Graph_SearchDijkstra
{
private:
//create typedefs for the node and edge types used by the graph
typedef typename graph_type::EdgeType Edge;
typedef typename graph_type::NodeType Node;
private:
const graph_type & m_Graph;
//this vector contains the edges that comprise the shortest path tree -
//a directed sub-tree of the graph that encapsulates the best paths from
//every node on the SPT to the source node.
std::vector<const Edge*> m_ShortestPathTree;
//this is indexed into by node index and holds the total cost of the best
//path found so far to the given node. For example, m_CostToThisNode[5]
//will hold the total cost of all the edges that comprise the best path
//to node 5 found so far in the search (if node 5 is present and has
//been visited of course).
std::vector<double> m_CostToThisNode;
//this is an indexed (by node) vector of "parent" edges leading to nodes
//connected to the SPT but that have not been added to the SPT yet.
std::vector<const Edge*> m_SearchFrontier;
int m_iSource;
int m_iTarget;
void Search();
public:
Graph_SearchDijkstra(const graph_type& graph,
int source,
int target = -1):m_Graph(graph),
m_ShortestPathTree(graph.NumNodes()),
m_SearchFrontier(graph.NumNodes()),
m_CostToThisNode(graph.NumNodes()),
m_iSource(source),
m_iTarget(target)
{
Search();
}
//returns the vector of edges defining the SPT. If a target is given
//in the constructor, then this will be the SPT comprising all the nodes
//examined before the target is found, else it will contain all the nodes
//in the graph.
std::vector<const Edge*> GetAllPaths()const;
//returns a vector of node indexes comprising the shortest path
//from the source to the target. It calculates the path by working
//backward through the SPT from the target node.
std::list<int> GetPathToTarget()const;
//returns the total cost to the target
double GetCostToTarget()const;
};
搜索（）：
template <class graph_type>
void Graph_SearchDijkstra<graph_type>::Search()
{
//create an indexed priority queue that sorts smallest to largest
//(front to back). Note that the maximum number of elements the iPQ
//may contain is NumNodes(). This is because no node can be represented
// on the queue more than once.
IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
//put the source node on the queue
pq.insert(m_iSource);
//while the queue is not empty
while(!pq.empty())
{
//get the lowest cost node from the queue. Don't forget, the return value
//is a *node index*, not the node itself. This node is the node not already
//on the SPT that is the closest to the source node
int NextClosestNode = pq.Pop();
//move this edge from the search frontier to the shortest path tree
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
//if the target has been found exit
if (NextClosestNode == m_iTarget) return;
//now to relax the edges. For each edge connected to the next closest node
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
//the total cost to the node this edge points to is the cost to the
//current node plus the cost of the edge connecting them.
double NewCost = m_CostToThisNode[NextClosestNode] + pE->Cost();
//if this edge has never been on the frontier make a note of the cost
//to reach the node it points to, then add the edge to the frontier
//and the destination node to the PQ.
if (m_SearchFrontier[pE->To()] == 0)
{
m_CostToThisNode[pE->To()] = NewCost;
pq.insert(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
//else test to see if the cost to reach the destination node via the
//current node is cheaper than the cheapest cost found so far. If
//this path is cheaper we assign the new cost to the destination
//node, update its entry in the PQ to reflect the change, and add the
//edge to the frontier
else if ((NewCost < m_CostToThisNode[pE->To()]) &&
(m_ShortestPathTree[pE->To()] == 0))
{
m_CostToThisNode[pE->To()] = NewCost;
//because the cost is less than it was previously, the PQ must be
//resorted to account for this.
pq.ChangePriority(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
}
}
}
什麼我不't get this is part：
//else test to see if the cost to reach the destination node via the
//current node is cheaper than the cheapest cost found so far. If
//this path is cheaper we assign the new cost to the destination
//node, update its entry in the PQ to reflect the change, and add the
//edge to the frontier
else if ((NewCost < m_CostToThisNode[pE->To()]) &&
(m_ShortestPathTree[pE->To()] == 0))
如果新的成本低於已經找到的成本，那麼爲什麼我們還要測試節點ha還沒有加入SPT？這似乎擊敗了檢查的目的？
僅供參考，在m_ShortestPathTree[pE->To()] == 0容器是具有指針爲每個索引的邊緣（或NULL）的矢量（該指數表示的節點）
可能是因爲它試圖避免無限循環的情況下，一個循環與否定e值存在於圖中？對於Dijkstra算法來說，這可能是該代碼嘗試處理的一個不好的輸入。 – Shahbaz 2012-03-12 17:18:40
@Shahbaz你可以詳細闡述一下嗎？對我而言，你的意思有點模糊。如果m_ShortestPathTree [pE-> To（）] == 0，這意味着在索引pE-> To（）（'nullptr'）處還沒有添加到SPT邊緣 – xcrypt 2012-03-12 17:36:49
我寫了解釋作爲答案 – Shahbaz 2012-03-12 17:53:15