最短路问题

最短路问题的类型与解决算法

最短路问题分为单源最短路(1-n的最短路)和多元汇最短路(源点=起点，汇点=终点)

1. 单元最短路

   1. 所有边权都是正数
      1. 朴素Dijkstra算法($O(n^2)$)，适合稠密图
      2. 堆优化的Dijkstra算法($O(m\log n)$)
   2. 存在负边权
      1. Bellman-Ford ($O(nm)$)
      2. SPFA 一般：($O(m)$)，最坏($O(nm)$)

2. 多元汇最短路 Floyd算法 $O(n^3)$

单元最短路

朴素Dijkstra算法

先加入起点

起点到其他点的距离都为无穷大，到自己是0

更新起点到其他点的距离，更新时判断是否最短

从未选择的点中选择距离最小的点，加入点集，重复上述操作，直至所有点都进入点集

算法实现

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int dist[N];
int n,m;
int g[N][N];
bool st[N];
void d(){
    memset(dist,0x3f,sizeof dist);
    int now = 1;
    dist[now] = 0;
    st[now] = true;
    for(int i =0;i<n;i++){
        for(int j = 1;j<=n;j++){
            dist[j] = min(dist[j],dist[now] + g[now][j]);
        }
        now = -1;
        for(int j = 1;j<=n;j++){
            if(!st[j] &&(now == -1 || dist[now] > dist[j]))
                now = j;
        }
        st[now] = true;
    }
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i =0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);
    }
    d();
    if(dist[n] == 0x3f3f3f3f)
        cout<<"-1";
    else
        cout<<dist[n];
    return 0;
}