algorithm - Dijkstra 的寻路算法

Question

我正在从一本书中学习寻路，但我发现了一些奇怪的说法。

为了完整起见，我将包含大部分代码，但请随意跳到第二部分 (Search())

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;
      }
    }
  }
}

我没有得到的是这部分:

//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) )

如果新成本低于已经找到的成本，那么为什么我们还要测试该节点是否已经添加到 SPT 中？这似乎违背了支票的目的？

仅供引用，在 m_ShortestPathTree[pE->To()] == 0 中，容器是一个向量，每个索引都有一个指向边(或 NULL)的指针(索引代表一个节点)

Answer 1

想象下图:

S --5-- A --2-- F
\      /
 -3  -4
  \ /
   B

并且您想从 S 转到 F。首先，让我告诉你 Dijkstra 算法假设图中没有负权重的循环。在我的示例中，此循环是 S -> B -> A -> S 或更简单的 S -> B -> S

如果你有这样一个循环，你可以在其中无限循环，你对 F 的成本会越来越低。这就是 Dijkstra 算法不能接受的原因。

现在，您如何检查它？就像您发布的代码一样。每次要更新节点的权重时，除了检查它是否变小的权重外，还要检查它是否不在接受列表中。如果是，那么你一定有一个负权重循环。否则，你怎么能继续前进并到达一个已经被接受的权重更小的节点？

让我们按照示例图上的算法([] 中的节点被接受):

没有有问题的if:

Starting Weights: S(0), A(inf), B(inf), F(inf)
- Accept S
New weights: [S(0)], A(5), B(-3), F(inf)
- Accept B
New weights: [S(-3)], A(-7), [B(-3)], F(inf)
- Accept A
New weights: [S(-3)], [A(-7)], [B(-11)], F(-5)
- Accept B again
New weights: [S(-14)], [A(-18)], [B(-11)], F(-5)
- Accept A again
... infinite loop

与有问题的if:

Starting Weights: S(0), A(inf), B(inf), F(inf)
- Accept S
New weights: [S(0)], A(5), B(-3), F(inf)
- Accept B (doesn't change S)
New weights: [S(0)], A(-7), [B(-3)], F(inf)
- Accept A (doesn't change S or B
New weights: [S(0)], [A(-7)], [B(-3)], F(-5)
- Accept F