#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
typedef struct SHORTRSTPATH_STRU
{
    int size;//图中节点的个数
    int**pathLen;//二位数组保存每对顶点中的最短路径长度
    int **nextVex;//二维数组保存vi到vj最短路径上vi后续节点的下标
}ShortPath;
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2,weight;
    scanf("%d%d%d",&vex1,&vex2,&weight);
    while(vex1!=0||vex2!=0)
    {
        graphMatrix->graph[vex1][vex2]=weight;
        scanf("%d%d%d",&vex1,&vex2,&weight);
    }

}

ShortPath*floyd(GraphMatrix*graphMatrix)
{
    int i,j,vex;
    ShortPath *shortPath=NULL;
    shortPath=(ShortPath*)malloc(sizeof(ShortPath));
    shortPath->size=graphMatrix->size;
    //分配空间二维数组
    shortPath->nextVex=(int**)malloc(sizeof(int*)*shortPath->size);
    for(i=0;i<shortPath->size;i++)
    shortPath->nextVex[i]=(int*)malloc(sizeof(int)*shortPath->size);
    //分配空间二维数组
    shortPath->pathLen=(int**)malloc(sizeof(int*)*shortPath->size);
    for(i=0;i<shortPath->size;i++)
        shortPath->pathLen[i]=(int*)malloc(sizeof(int)*shortPath->size);
    //初始化
    for(i=0;i<shortPath->size;i++)
    {
        for(j=0;j<shortPath->size;j++)
        {   
            //为了不破坏图的原有结构，使用辅助数组进行数据的迭代
            shortPath->pathLen[i][j]=graphMatrix->graph[i][j];
            if(shortPath->pathLen[i][j]==MAX)
                shortPath->nextVex[i][j]=-1;
            else
                shortPath->nextVex[i][j]=j;
        }
    }
    //正式开始计算
    for(vex=0;vex<graphMatrix->size;vex++)
    {
        for(i=0;i<graphMatrix->size;i++)
        {
            for(j=0;j<graphMatrix->size;j++)
            {
                if(shortPath->pathLen[i][vex]==MAX||shortPath->pathLen[vex][j]==MAX)
                    continue;
                    //路径更短，则更新
                if(shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j]<shortPath->pathLen[i][j])
                {
                    shortPath->pathLen[i][j]=shortPath->pathLen[i][vex]+shortPath->pathLen[vex][j];
                    shortPath->nextVex[i][j]=shortPath->nextVex[i][vex];
                }
            }
        }

    }
    return shortPath;
}
int main()
{  
    //最短路径测试
   GraphMatrix*graphMatrix=NULL;
   ShortPath*shortPath=NULL;
   int i,j,k,e,maxdistan[6],min=0;
   graphMatrix=InitGraph(6);
   ReadMatrix(graphMatrix);//读图
   shortPath=floyd(graphMatrix);//使用floyd算法
   for(i=0;i<graphMatrix->size;i++)
   {   
       
       for(j=0;j<graphMatrix->size;j++)
       {
           if(i!=j&&shortPath->pathLen[i][j]!=MAX)
           {
               printf("从%d到%d的最短路径长度为%d,具体路径为",i,j,shortPath->pathLen[i][j]);
               printf("%d",i);//输出起点
               k=i;//从起点出发，寻找完整路径
               while(k!=j)
               {
                   k=shortPath->nextVex[k][j];
                   printf("->%d",k);//将途径点输出
               }
               printf("\n");
               /*if(min<shortPath->pathLen[i][j])
               {
                   min=shortPath->pathLen[i][j];
                   maxdistan[i]=min;
               }
               if(i==0)
             {
               printf("%d->%d:%d",i,j,shortPath->pathLen[i][j]);
               printf("\n");
               printf("%d",i);
               k=i;
               while(k!=j)
               {
                   k=shortPath->nextVex[k][j];
                   printf("->%d",k);
               }
               printf("\n");
             }*/
           }
       }
   }
   return 0;
}

    Floyd算法又称为弗洛伊德算法、插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

课题名称：设备更新，使总的支付费用最少

    工厂的某台机器可连续工作四年，决策者每年年初都要决定机器是否需要更新。若更新，就要支付购置费用；若不更新，则要支付维修与运行费用，且随着机器使用年限的增加维修与运行费用逐年增多。计划期（4年）中每年年初的购置价格及各个年限内维修与运行费用由表1给出，

（1）试制订今后4年的机器更新计划，使总的支付费用最少。

表1

可将此问题看成一个最短路问题。设 v1 和 v5 分别表示计划期的始点和终点（v5 可理解为第4年年末）。下图中各边的值(vi,vj)表示在第 i 年初购进的机器使用到第 j 年初（即第 j-1 年底），(vi,vj)的值可由表1的数据计算得到。因此，把求最优设备更新问题转化为求从 i 到 j 的最短路问题。

(vi,vj)的值计算示例：

（v1,v2） = 2.5（第1年初的购置费）+1（使用第一年的维修费） = 3.5；

（v3,v5） = 2.8（第3年初的购置费）+1（使用第一年的维修费）+1.5（使用第二年的维修费） = 5.3；

Matlab求解

Matlab程序：

a=[0 3.5 5 7 11;inf 0 3.6 5.1 7.1;inf inf 0 3.8 5.3;inf inf inf 0 4.1;inf inf inf inf 0];
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end
    end
end
for k=1:n
    for i=1:n
        for j=1:n
            if D(i,k)+D(k,j)<D(i,j)
                D(i,j)=D(i,k)+D(k,j);
                path(i,j)=path(i,k);
            end
        end
    end
end
D;path;

Matlab运行结果：

D =
         0    3.5000    5.0000    7.0000   10.3000
       Inf         0    3.6000    5.1000    7.1000
       Inf       Inf         0    3.8000    5.3000
       Inf       Inf       Inf         0    4.1000
       Inf       Inf       Inf       Inf         0
>> path
path =
     1     2     3     4     3
     0     2     3     4     5
     0     0     3     4     5
     0     0     0     4     5
     0     0     0     0     5

解得方案：最短路（v1,v3,v5），即计划期内机器更新最优计划为第1年、第3年初各购进一台新机器，4年总的支付费用为10.3万元。

新问题来了！

按照上述方案，第3年初购置新机器，那么旧机器是否可以低价处理掉呢？这样也更加符合实际。如果已知不同役龄机器年末的处理价格如表2所示，那么在这计划期内机器的最优更新计划又会怎样？

表2

类似上面的处理方式，可转化为求下图中从 v1 到 v5 的最短路问题。

Matlab求解

Matlab程序：

a=[0 1.5 3.4 5.7 9.5;inf 0 1.6 3.5 5.8;inf inf 0 1.8 3.7;inf inf inf 0 3.1;inf inf inf inf 0];
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end
    end
end
for k=1:n
    for i=1:n
        for j=1:n
            if D(i,k)+D(k,j)<D(i,j)
                D(i,j)=D(i,k)+D(k,j);
                path(i,j)=path(i,k);
            end
        end
    end
end
D;path;

Matlab运行结果：

D =
         0    1.5000    3.1000    4.9000    6.8000
       Inf         0    1.6000    3.4000    5.3000
       Inf       Inf         0    1.8000    3.7000
       Inf       Inf       Inf         0    3.1000
       Inf       Inf       Inf       Inf         0
>> path
path =
     1     2     2     2     2
     0     2     3     3     3
     0     0     3     4     5
     0     0     0     4     5
     0     0     0     0     5

即最后解得：最短路 （v1,v2,v3,v5），即计划期内机器更新最优计划为第1年初购进一台新机器并在第2年初处理掉，第2年初购进一台新机器并在第3年初处理掉，第3年初购进一台新机器，4年总的支付费用为6.8万元。

内容很多，消化一下吧，希望可以为你所用！