您的位置: 首页  >  文章  >  Dijkstra

Dijkstra

分类: 文章 • 2024-06-07 21:51:40

  1. 问题
    给定一个有权值有向图，指定一个顶点，求出其到另一个指定顶点的最短距离。

  2. 解析
    DijkstraDijkstra

  3. 设计
    初始化数组g[][],d[],p[];
    For（循环次数小于等于最多边数）
    {
    For（） 找出未存放的最小顶点并标记
    For（）更新d数组
    }

  4. 分析
    O（elogv）//v为顶点数

  5. 源码
    https://github.com/CunHua-YYT/CunHua-YYT/blob/master/Dijkstra.cpp

相关推荐