[图] Prim与Dijkstra的异同

╰半夏微凉° 2023-05-31 06:42 17阅读 0赞

【两个算法的回顾】

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>Prim</th> 
   <th>Dijkstra</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>用途</td> 
   <td>树中所有边的权值之和最小</td> 
   <td>某个点到任何其他点的距离都是最短的</td> 
  </tr> 
  <tr> 
   <td>思想</td> 
   <td>①以顶点为操作对象，每次选择一个顶点并入子图；<br>②顶点的选择依据：<strong>子图顶点</strong>到<strong>其他顶点</strong>的<strong>最短边</strong></td> 
   <td>①以顶点为操作对象，每次选择一个顶点并入子图；<br>②顶点选择依据：<strong>起点</strong>到<strong>其他顶点</strong>的<strong>最短路径</strong></td> 
  </tr> 
  <tr> 
   <td>数据结构</td> 
   <td>①子图vest[i]：结点i是否已并入生成树；<br>②lowcost[i]：结点i到子树的最短边权重</td> 
   <td>①子图set[i]：结点i是否在子图中<br>②dist[i]：起点v0到结点i的最短路径值为dist[i]<br>③path[i]：为该路径中i的前一个结点</td> 
  </tr> 
  <tr> 
   <td>代码</td> 
   <td><img src="https://img-blog.csdnimg.cn/20191023111031870.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
   <td><img src="https://img-blog.csdnimg.cn/20191023125654990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
  </tr> 
 </tbody> 
</table>

【两者的异同】

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>Prim</th> 
   <th>Dijkstra</th> 
   <th>两者相同之处</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>适用性</td> 
   <td>无向连通图</td> 
   <td>无向图、有向图（不能处理负权值）</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>用途</td> 
   <td>树中所有边的权值之和最小</td> 
   <td>某个点到任何其他点的距离都是最短的</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>松弛操作</td> 
   <td>考虑的是<strong>相邻结点</strong>的权值（每次选择是最小边）<br>即每个点<strong>直连</strong>其他点的最小值（无中转点）</td> 
   <td>考虑<strong>起点到其他点</strong>的权值（每次选择的是最短路径）<br>即<strong>每个点到其他点</strong>的最小值（有中转点）</td> 
   <td>两者的每一步都是选择最小</td> 
  </tr> 
  <tr> 
   <td>更新操作</td> 
   <td><img src="https://img-blog.csdnimg.cn/20191023125907737.png" alt="在这里插入图片描述"></td> 
   <td><img src="https://img-blog.csdnimg.cn/20191023125850384.png" alt="在这里插入图片描述"></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>生成的结果</td> 
   <td>图的最小生成树</td> 
   <td>构建单源点的最短路径树</td> 
   <td>都是生成树，结果<strong>可能</strong>相同</td> 
  </tr> 
  <tr> 
   <td>思想</td> 
   <td>通过贪婪来选择<strong>最小的边</strong>，而Prim的每个子树都是最小生成树说明满足线性规划的两个条件</td> 
   <td>通过线性规划缓存了最优子路径的解，每一步也通过贪婪算法来选择最小的边</td> 
   <td>两者都使用<strong>贪婪和线性规划</strong></td> 
  </tr> 
  <tr> 
   <td>例子对比</td> 
   <td>为N个村庄修路，花销最小</td> 
   <td>单个村庄到其他村庄的最短路径</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

【相关解释】

*  【贪婪】一个局部最优解也是全局最优解
 *  【线性规划】主问题包含了n个子问题，而且其中有重叠的子问题

【参考文章】

*  [博文：Dijkstra算法与Prim算法的异同][Dijkstra_Prim]

[Dijkstra_Prim]: https://blog.csdn.net/qq284565035/article/details/51583314