吴文虎图论学习日志——第二章

最短路径的算法及其应用：

算法有很多，包括上面没有讲到的和讲到的：

SSSP（单源最短路径）：1.标号法 2.Dijkstra(可以用heap优化) 3.Bellman_ford(可以检测负环) 4.SPFA(可以检测负环,还可以继续优化，不过还没学)

所有点对的最短路径：1.可以求N次SSSP 2.Floyd算法

该章提到的应用问题：

1. 求图的中心点：

中心点定义：找出一个顶点，使得其到所有其他的顶点的最短路径的最大值最小。

求法：求出所有顶点对的最短路径，求出每个顶点到其他所有顶点的最短路径的最大值，从中选出最小的那个，用Floyd算法求解，时间复杂度为O(N^3).

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int inf = 0xffffff;
const int MAXN = 110;
#define MIN(a,b) (a)>(b)?(b):(a)
int g[MAXN][MAXN],d[MAXN][MAXN];
void init()
{
     memset(g,0,sizeof(g));
} 
void Floyd(int n)
{
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
         {
             if(g[i][j])d[i][j]=g[i][j];
             else d[i][j]=inf;
             if(i==j)d[i][j]=0;
         }
     }
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
         {
             for(int k=0;k<n;k++)
             {
                  d[i][k] = MIN(d[i][k],d[i][j]+d[j][k]);
             }        
         }
     }
}
int CenterPoint(int n)
{
    int best=inf+1,best_i;
    for(int i=0;i<n;i++)
    {
        int max = -1; 
        for(int j=0;j<n;j++)
        {
            if(d[i][j]>max)
            {
                max = d[i][j];
            }
        }
        if(max<best)
        {
            best = max;
            best_i = i;
        }
    }
    return best_i;
}
int main()
{
    int n;
    init();
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>g[i][j];
        }
    }
    Floyd(n);
    int point = CenterPoint(n);
    cout<<point<<endl;
    system("pause");
    return 0;
}

2.求图的P中心点：

P中心点的定义：记图的顶点集V的一个含有P个元素的子集为S，使得集合V-S中的顶点到S中顶点的最短路径的最大值最小的集合S，就是图的P中心点。

求法：求出所有顶点对的最短路径，枚举S的每一种情况，记录下集合V-S中的顶点到S中顶点的最短路径的最大值，然后从所有的情况中选出最小的种顶点的组 合方式，就是图的P中心点。

注意：需要枚举排列，复杂度很高，目前还没有有效算法。

代码略。

3.求图的中央点：

中央点的定义：记顶点V到其他各顶点的最短距离为d(x)，每前进单位距离需要的代价为k，使得 所有的 k*d(x)的和最小的顶点就是图的中央点。

求法：求出所有顶点对的最短路径，求出每个顶点到其他所有顶点的（最短路径*代价）的和，选出使得该和最小的顶点，就是图的中央点。用Floyd算法，时 间复杂度为O(N^3).

代码（把前面代码的CenterPoint换成该函数即可，这里K取1）

int ZhongYangPoint(int n)
{
    int best = inf,best_i;
    for(int i=0;i<n;i++)
    {
        int sum = 0; 
        for(int j=0;j<n;j++)
        {
            sum+=d[i][j];
        }
        if(sum<best)
        {
            best = sum;
            best_i = i;
        }
    }
    return best_i;
}