图的算法

求起点到其他所有点的最短距离：

• Bellman_Ford算法

//初始化：
    //对于起点 dis[vs]=0
    //对于其他点 dis[i]=INF
//遍历nodenum - 1遍
    //遍历所有边
      if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost)
        dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
        pre[edge[j].v] = edge[j].u;
//检查是否有负权回路
//在遍历了nodenum - 1遍后
  //如果还有
  dis[edge[j].v] > dis[edge[j].u] + edge[j].cost
  //则存在负回路，没有最短路径

• Dijkstra

//遍历nodenum - 1遍
    //找到最短距离dist[j]和该点j，即到该点最短距离已经求出
    //更新剩下没有找到最短路径的点，如果从原点到j再到该点距离比之前更短，那么更新dist[i]和

最大网络流算法

• Edmonds_Karp

while (1)
{
    //初始化：p和pre置零，p.push(start)
    //p不为空：
        //对所有p中元素遍历，将和该结点相邻的所有点push进p，并记pre[i]=该点
    if (pre[end] == 0)//找完了
        break;
    //否则更新
    //从end到start，遍历pre[i]，找到最小的dp[i][j]=minflow
    //更新dp，从end到start
    {
        dp[pre[i]][i] -= minflow;
        dp[i][pre[i]] += minflow;
    }
}

代码：http://pan.baidu.com/s/1dF7qbAh

最小生成树算法

• Prim普利姆算法
  每次都连接和已经标记的所有点的距离最短的那个点。
• Kruskal克鲁斯卡尔算法
  每次只找没有标记的边中边长最短的，不管已经标记过的点。如果选择该边后构成回路则放弃该边重新选择。