单源最短路

给定一个带权有向图 G=(V,E) , 还给定 V 中的一个顶点，称为源。计算从源点出发，到达其他顶点的最短路径的长度。
Dijkstra算法：该算法要求图中不存在负权边。
算法思想：

1. S为空集，G为图
2. u为G中最短路径估计最小节点，将u加入S中
3. 遍历G中与u相连的节点v, 更新v的最短路径估计

代码实现：

void Dijkstra(int cur)
{
    vis[cur] = 1;
    for(int i=1; i<=n; i++)
        dist[i] = map[cur][i];
    dist[cur] = 0;
    for(int i=1; i<n; i++)  //添加剩下的n-1个节点
    {
        int k;
        int minval = INF;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j] && dist[j] < minval)
            {
                minval = dist[j];
                k = j;   //记录最短路径估计节点
            }
        }
        vis[k] = 1;  //加入S集合
        for(int j=1; j<=n; j++)  //更新与之相连节点的最短路径估计
        {
            if(!vis[j] && dist[j]>dist[k]+map[k][j])
                dist[j] = dist[k] + map[k][j];
        }
    }
    
}

时间复杂度： 不采用优先队列，为O（n^2）

Bellman-Ford算法

• 一般解决单源最短路径问题，边权可以为负值。
• 可以用来判断图中是否存在负权回路。

算法思想：
核心思想是松弛，反复用已有的边更新最短距离。如果dist[u]和dist[v]满足dist[v]>dist[u]+map[u][v],dist[v]就应该被更新为dist[u]+map[u][v]。反复的利用该式对dist数组进行松弛，如果没有负权回路的话，应当会在n-1次松弛后结束。
代码实现：

void Relax(int s, int t, int w)
{
    if(dist[t] > dist[s] + w)
    {
        dist[t] = dist[s] + w;
    }
}

//判断是否存在负权回路
bool Bellman_Ford(int cur)
{
    for(int i=0; i<n; i++)
        dist[i] = INF;
    dist[cur] = 0;
    for(int i=0; i<n-1; i++)   //n为节点个数，松弛n-1次
    {
        for(int j=0; j<m; j++)  //m为边的数目
            Relax(edge[i].s, edge[i].t, edge[i].w);
    }
    
    for(int i=0; i<m; i++)
    {
        if(dist[edge[i].t] > dist[edge[i].s] + edge[i].w)  //第n次操作仍能松弛，则存在负权回路
            return true;
    }
    return false;
    
}

/*
3 3
1 2 3
1 3 4
3 2 -2
*/

时间复杂度：O（V*E）

总结：

• 松弛：每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过n-1条边，所以需要循环n-1次。
• 负权环判定：因为负权环可以无限制的降低总花费，所以如果发现第n操作仍可降低花销，就一定存在负权回路。

Bellman-Ford和Dijkstra算法类似，都是以松弛操作为基础，即估计最短路径值渐渐被更加准确的值替代，直到得到最优解。
但是Dijkstra是以贪心法选取未被处理的具有最小权值的节点，然后对其出边进行松弛操作；而Bellman-Ford是对所有边进行松弛操作，共n-1次。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。