dijkstra
1.边权为正值；2可以存在自环；3.单源
代码模板：

void djkstra()
{
    memset(dist,0x3f,sizeof dist);

    dist[start]=0;
    st[start]=true;

    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j] and (t==-1 || dist[t]>dist[j]))
            {
                t=j;
            }
        }
        st[t]=true;

        for(int j=1;j<=n;j++)
        {
            if(dist[j]>dsit[t]+g[t][j])
            {
                dist[j]=dist[t]+g[t][j];
            }
        }
    }
}

堆优化版

void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>>heap;

    heap.push({0,start});
    dist[start]=0;

    while(heap.size())
    {
        PII t=heap.top()
        heap.pop();

        int ver=t.second;
        st[ver]=true;

        for(int i=1;i<=n;i++)
        {
            if(dist[i]>dist[ver]+g[ver][j])
            {
                dist[i]=dist[ver]+g[ver][j];
                heap.push({dist[j],j});
            }
        }
    }
}

dijkstra的标记数组代表确没确定最终的距离

bellman
1.有边数限制；2边权可以为负值；3可以存在自环；4.单源；5可能 存在负权回路
模板：
不需要建图，只需要存储下来每一条边，也不像最小生成树一样排序

struct Edge
{
    int a, b, c;
}edges[M];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[start] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

spfa
1.边权可以为负；2.可以存在自环；3.单源；4.不存在负权回路
模板

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;

    queue<int> q;
    q.push(start);
    st[start] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

这里的标记数组代表在没在队列里面，最后队列会为空

模拟循环队列：

int dd=0,tt=1;
...
if(dd==N)dd=0;
....
while(dd!=tt)
{
    ...
    if(tt==N)tt=0;
}

spfa可以通过统计每个点的更新次数来判断有无负环；

if (dist[j] > dist[t] + w[i])
{
    dist[j] = dist[t] + w[i];
    cnt[j] = cnt[t] + 1;

    if (cnt[j] >= n) return true;
    if (!st[j])
    {
            q.push(j);
            st[j] = true;
    }
}

floyd
1.多源；2.边权可以为负数；3.可以存在自环；4.不存在负环
模板

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

dp与最短路模型
dp和图论的交集是拓扑图，因为dp只能实现不存在环的模型，而不存在环的充要条件就是这个图是拓扑图；
一些不存在环的dp问题可以用图论的最短路模型来解决