最短路问题可以分为两种，单源最短路和多源汇最短路。
单源最短路问题分为：正权边问题和存在负权边的问题。
(n为点数，m为边)
正权边问题：
1.朴素dijkstra算法
时间复杂度为O(n^2),适用于稠密图，通常用邻接矩阵存图。
核心代码。

int g[N][N];//存图
int dis[N];//存起点到当前点的距离
bool st[N];//判断点是否被更新
int dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;//初始化起点
    for(int i=0;i<n-1;++i)
    {
        int t=-1;
        for(int j=1;j<=n;++j)
        if(!st[j]&&(t==-1||dis[j]<dis[t]))
        t=j;//选取更小的的距离来更新其他点
        st[t]=true;
        for(int j=1;j<=n;++j)
        {

            dis[j]=min(dis[j],dis[t]+g[t][j]);
        }//更新每个点与起点的距离
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    else return dis[n];
}

2.堆优化版的dijkstra算法
时间复杂度为O(mlogn),适用于稀疏图，通常用邻接表存图，用于处理权值为正值。
核心代码。

int h[N],e[N],ne[N],idx;//邻接表存图
int w[N];//存a->b的距离
int dis[N];
bool st[N];//判断当前节点是否被更新
int n,m;
typedef pair<int,int> PII;
void add(int a,int b,int c)
{
    e[idx]=b;ne[idx]=h[a];w[idx]=c;
    h[a]=idx++;
}//存图
int dijkstra()
{
    memset(dis, 0x3f,sizeof dis);
    dis[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;//使用优先队列，建立小根堆
    heap.push({0,1});//优先队列存起点
    while(heap.size())//优先队列中对每一个点只储存一次，即堆顶为最小值用最小距离来更新邻接点
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second;int dist=t.first;
        if(st[ver])
        continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                if(!st[j])
                heap.push({dis[j],j});
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    else return dis[n];
}

存在负权边问题：
1.bellman_ford算法
时间复杂度为O(nm),可以用结构体存图
核心代码。

int dis[N];bool st[N];int n,m,k;//k是指到达最短距离，走了不超过k条边
struct Edge
{
    int a,b,c;
}edge[M];
int last[N];
int bellman_ford()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=1;i<=k;++i)
    {
        memcpy(last,dis,sizeof dis);//防止串联，即一个循环内我们只能对dis每个点更新一步，
        for(int i=1;i<=m;++i)
        {
            auto t=edge[i];
            dis[t.b]=min(dis[t.b],last[t.a]+t.c);
        }
    }
    if(dis[n]>0x3f3f3f3f/2) return -1;//具体题目具体判断结束条件。
    else return dis[n];
}

2.spfa算法
时间复杂度平均情况下为O(m),最坏情况下为O(nm),也是队列优化的bellman_ford算法。同样spfa算法可以判断图中是否有负权回路。
核心代码。

int e[N],ne[N],idx,w[N],h[N];
int dis[N];
bool st[N];int n,m;
void add(int a,int b,int c)
{
    e[idx]=b;ne[idx]=h[a];w[idx]=c;
    h[a]=idx++;
}//建图
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    queue<int> p;
    p.push(1);
    st[1]=true;
    while(p.size())//可以多次入队
    {
        int x=p.front();
        p.pop();st[x]=false;
        for(int i=h[x];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[x]+w[i])
            {
                dis[j]=dis[x]+w[i];
                if(!st[j]){
                p.push(j);
                st[j]=true;
                }
            }
        }
    }
    return dis[n];
}

多源汇最短路问题：
1.floyd算法
时间复杂度为O(n^3);
核心代码。

for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
            //初始化，dis[i][j]表示i到j的距离
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
}