最短路问题就是求 【一个点到另一个点的最短路径】 分为单源最短路（一个点到各个点之间的距离）和多源最短路（任意两点之间的距离）

1.Dijkstra算法

使用广度优先搜索，解决【赋权有向图】或【无向图的单源最短路径】问题，不能出现负边 基于【贪心】思想

1.1 内容

// 用 d i s [ ] dis[] dis[]数组储存从顶点到其他点的路径，通过一步步遍历比较，不断更新（保留最小的，改变较大的），最后得到dis即为所求

求从v1到各个点的最短路： step1：初始化dis step2：找最小的，固定，从这个点往外遍历 此时，离起点最近的那个点一定是最短的，因为没有负边，不可能经过其他的点了 ① v3最小，意思是从v1到v3的所有路径中，一定是现在的最短，所以把<v1,v3>确定下来了 ② 从v3开始遍历，发现v4，v4没有被遍历过，比较<v1,v3,v4>（经过v3到达）和<v1,v4>（由顶点直接到达）的最短距离（松弛操作），更新v4 step3：找最小的，固定 （重复step2中的思想往下做就行啦）

不断取出离顶点最近，并且没有被访问过的点

① v5最小，固定 ② 遍历v5，发现<v5,v4>和<v5,v6>，比较<v1,v5,v4><v1,v4>和<v1,v5,v6><v1,v6>（顶点直接到达的和经过v5到达的）更新 step4：v4最小，固定，遍历v4发现v6，比较<v1,v6>和<v1,v4,v6><v1,v5,v6>，更新

1.2 堆优化

时间复杂度为 O ( m l o g m ) O(mlogm) O(mlogm)

结构体

struct Edge
{
          
   
    int to, dis;
    Edge(int to,int dis):to(to),dis(dis){
          
   }

    bool operator<(const Edge &a) const
    {
          
    return a.dis < dis; }
};
} e[MAXX];

过程

void dijstra()
{
          
   
    priority_queue<Node> pq;
    pq.push(Node{
          
   s, 0});
    dist[s] = 0;
    while (!pq.empty())
    {
          
   
        Node n1 = pq.top();
        pq.pop();
        int tmp = n1.id;
        if (vis[tmp])
            continue;
        vis[tmp] = 1;
        for (int i = head[tmp]; i; i = e[i].next)
        {
          
   
            int j = e[i].to;
            if ( e[i].dis + dist[tmp] < dist[j])
            {
          
   
                dist[j] = e[i].dis + dist[tmp]; //dist开longlong，可能是数据会溢出
                pq.push(Node{
          
   j, dist[j]});
            }
        }
    }
}

打印路径

用一个pre[]数组存储每个点的父节点即可

1.3题目

3. 最短路——floyd算法

内容

使用传递闭包的性质

for(int k = 1 ; k <= n ; k++)
    {
          
   
        for(int i = 1 ; i <= n ; i++)
        {
          
   
            for(int j = 1 ; j <= n ; j++)
            {
          
   
                road[i][j] = min(road[i][j],road[i][k]+road[k][j]);
            }
        }
    }

特点

三重循环，所以不适合处理大数据，可以为负

题目