单元路劲及多元路径的搜索
 
//单元路劲及多元路径的搜索
 
#include
 
# define N 10
 
# define MAX 10000
 
typedef struct nam
 
{
 
int number;
 
char ch;
 
}T;
 
typedef struct name
 
{
 
int person,relate;
 
int adj[N][N],weight[N][N],preced[N][N],p[N],A[N][N];
 
T dian[N];
 
}TT;
 
void creat(TT *map)
 
{
 
int i,j,first,last,t;
 
char h;
 
for(i=1;i<=map->person;i++)
 
{
 
cout<
 
cin>>h;
 
map->dian[i].ch=h;
 
map->dian[i].number=i;
 
for(j=1;j<=map->person;j++)
 
{
 
map->adj[i+1][j+1]=0;map->weight[i][j]=MAX,map->A[i][j]=MAX;
 
}
 
}
 
cout<
 
for(i=1;i<=map->person;i++)
 
cout<dian[i].ch<"<
 
for(i=1;i<=map->relate;i++)
 
{
 
cout<>first>>last>>t;
 
if(first>map->person&&last>map->person)
 
{ cout<person<
 
cin>>first>>last>>t;
 
}
 
map->adj[first][last]=1;map->weight[first][last]=t;map->A[first][last]=t;
 
}

**
 
Floyd算法求解多元最短路径问题
 
**
 问题描述：
 对于多个目标地A，B，C…，求解两地之间的最短路径问题，例如求解 A-C的距离，常见的解有两种，一种是直接由A-C,另一种是经过某个中转地再到达目的地，即A-B-C，其中中转地可以是n个。
 
floyd算法解释：
 floyd算法的核心思想是将多地间的距离构建为一个距离矩阵（即二维数组），然后再通过遍历方法，刷新距离矩阵，下面通过一组实例来解释：
 例如有A，B，C，D四个目标地点，其相互间的距离为矩阵中所示，
 其中4行1列的“7”，与1行4列的“7”，均表示由A-D的距离为7，但是我们发现，若需要从A地去D地，若途径C地，需要“1”步，再由C去D，需要“5”步，则采用A-C-D的路线，共需要“6”步，最短路径的问题从而产生。所以算法的思想就是，遍历找到合适的中转点，使得由出发地去目的地的路程最短。
 
算法实现：
 step1、建立原始距离矩阵：
 
int map[4][4] = {
    0,4,1,7,
    4,0,2,3,
    1,2,0,5,
    7,3,5,0
};
 
step2、floyd遍历实现：
 
for(mid = 0 ; mid < 4 ; mid++)
{
for(start = 0 ; start < 4 ; start ++)
{
    for(end = 0 ;end<4 ; end ++)
    {
        if((start == end)||(start == mid)||(end == mid)) continue ; 
        if(map[start][mid] + map[mid][end] <map[start][end])
        {
            map[start][end]= map[start][mid] + map[mid][end] ; 
        } 
    }
}
}
 
step3、输出最短距离矩阵：
 
完整的代码为：
 
#include <iostream>

using namespace std ; 

int main()
{
int map[4][4] = {
    0,4,1,7,
    4,0,2,3,
    1,2,0,5,
    7,3,5,0
};

cout<<"before floyd"<<endl ; 
for(int i = 0 ; i < 4 ; i++)
{
    for(int j = 0 ; j < 4 ; j ++)
    {
        cout<<map[i][j]<<" " ; 
    }
    cout<<endl ; 
}

cout<<"after floyd"<<endl ; 

int mid = 0 ; 
int start = 0 ; 
int end = 0 ; 

for(mid = 0 ; mid < 4 ; mid++)
{
for(start = 0 ; start < 4 ; start ++)
{
    for(end = 0 ;end<4 ; end ++)
    {
        if((start == end)||(start == mid)||(end == mid)) continue ; 
        if(map[start][mid] + map[mid][end] <map[start][end])
        {
            map[start][end]= map[start][mid] + map[mid][end] ; 
        } 
    }
}
}

for(int i = 0 ; i < 4 ; i++)
{
    for(int j = 0 ; j < 4 ; j ++)
    {
        cout<<map[i][j]<<" " ; 
    }
    cout<<endl ; 
}


    system("pause");
    return 0 ;
}
 
测试输出结果：
 
 floyd的核心代码其实就是循环遍历的那几行，找到合适的中转点，使得从起始地至目的地的距离最短，适合求解多源最短路径问题，欢迎大家交流。

如图在xy平面
 
经过点（2,0）和（0,2）的圆弧所在的曲面与f(x,y)曲面之间的面积
 
和x轴0-2与f(x,y)，y轴0-2与f(x,y)面积的和
 
${\oint }_c(x+y^2)ds$
 

 而它的面积就等于三段面积的和
 
 先看圆弧部分
 
如何构建x，y
 
$x^2+y^2=1$表示圆，我们只考虑正半轴
 
因为这里半径是2，t的边界是0-$\pi /2$
 
所以我们得到x，y
 
 先求出ds，带入
 
 带入x，y，简化表达式
 
 有三角函数的平方关系
 
 利用平方关系继续简化
 
 得到
 
 而乘以dt即求原函数，cos的原函数等于sin
 
 求积分，t=$\pi /2$的值减去t=0的值
 
而 ，$sin\pi =0,sin(\frac{\pi }{2})=1$
 
得到这段积分等于 :
 
4+2$\pi$
 
 再来看第二段的积分
 
第二段c2的积分在y轴上
 
因此我们构建x，y函数
 
x=0
 
y=2-t
 
t的边界定义在0<=t<=2
 
 
 先求ds
 
带入ds，x，y
 
又由$（a-b{）}^2=a^2-2ab+b^2$
 

 乘以dt，即求原函数
 
 带入t=2减去t=0求积分
 
求得$c_2=8/3$
 
再来求c3的积分
 
先求ds
 
根号下等于1，乘以dt
 
 带入x，y，ds：
 
等于t*dt，即求t的原函数
 
 t的原函数可以表示成$\frac{1}{2}{t}^2$
 
带入t=2减去t=0时求得积分等于2
 
 

多源最短路径——Floyd-Warshall算法
 
首先分析这张图
 
 
就拿从1到3，可以直接1->3，也可以1->2->3,我们发现，通过一个“中转”的2，1->3路径会变短。
 
可以在一个路径中插入另一个顶点，这样可能会比直接过去的路径更短，假设每个顶点都经过顶点2中转，可以有这样的语句。
 
我们用二维数组graph[][]存储图
 
int i;
int j;
for(i=1;i<=n;++i){

    for(j=1;j<=n;++j){

        if(graph[i][j]>graph[i][2]+graph[2][j])//通过中转路径变短了
            graph[i][j]=graph[i][2]+graph[2][j];//则将从i到j的路径长度改为中转后的较短路径
    }
}
 
中转顶点可以是图中的任意一个顶点，所以将所有顶点做一次中转顶点 即可以将用一个循环变量来当作中转点
 
int i;
int j;
int k;
for(k=1;k<=n;++k){
    for(i=1;i<=n;++i){

        for(j=1;j<=n;++j){

            if(graph[i][j]>graph[i][2]+graph[2][j])//通过中转路径变短了
                graph[i][j]=graph[i][2]+graph[2][j];//则将从i到j的路径长度改为中转后的较短路径
        }
    }
}
 
完整代码如下：
 
#include <stdio.h>

const int INF=999999999;

int main(void){

    int graph[10][10];
    int n,m;//n个顶点，m条边
    printf("请输入定点数与边数：");
    scanf("%d%d",&n,&m);

    //初始化二维数组 
    for(int i=1;i<=n;++i){

        for(int j=1;j<=n;++j){

            graph[i][j]=INF;
        }
        graph[i][i]=0;
    }

    for(int i=1;i<=m;++i){

        int s,e;
        printf("第%d条边及其权值：",i );
        scanf("%d%d",&s,&e);
        scanf("%d",&graph[s][e]); 
    }

    /*********核心部分*********/
    int i,j,k;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k){

                if(graph[j][i]!=INF && graph[i][k]!=INF && graph[j][i]+graph[i][k]<graph[j][k])
                    graph[j][k]=graph[j][i]+graph[i][k];
            } 
    /*************************/ 

    printf("\n===========================\n");
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j){

            if(graph[i][j]!=INF && graph[i][j])
                printf("%d-->%d  %d\n",i,j,graph[i][j]);
        }

    return 0;
}
 
虽然用插一个中转点来引出这段代码，但是最短路径不一定全是只会有一个中转点。
 
举个栗子：假设一个最短路径是1->3->5->7,上述算法先找出从1到5的最短路径是1->3->5，现在的graph[1][5]被更新成为了grap[1][3]+graph[3][5]，接下来计算1->7的最短路径时上述算法算出的时1->5->7,这里的1->5实际上是1->3->5。这样说可能有点乱，希望的对理解这个算法有点帮助。