擅长:python、mysql、java
<p>假设您的图表如下所示:</p>
<pre><code> 9
S - G
\ /
1\ /1
\ /
W
</code></pre>
<p>您需要从起始节点<code>S</code>到目标节点<code>G</code>,路径尽可能便宜。S-G边的代价为9,而连接到分段点<code>W</code>的每条边的代价是2。</p>
<p>您的算法将通过<code>S</code>的邻居来向边界添加节点,找到<code>G</code>,并立即返回昂贵的直接S-G路径,而不必找到通过路径<code>W</code>的路径。</p>
<p>相反,当您<code>pop</code>来自优先级队列的节点时,需要对该节点执行目标测试。在这一点上,可以保证您已经找到了到节点的<strong>最便宜的</strong>路径,而不仅仅是一些到节点的<em>路径。</p>