发一道题目，过几天再发答案！大家试一试，很有代表性的题

建议大家先看一看Floyd算法，这道题主要是测试这个算法！

问题 K: 数据结构（C语言版）算法7.16__最短路径Floyd
题目描述 求带权有向图中任意2个顶点之间的最短路径。输入先输入顶点个数及边的条数；然后依次输入各条边的信息，包括起点，终点，权值。输出输出任意2点间的路径长度信息。
1）如果存在路径，则输出路径长度，如“1->2:2”表示顶点1至顶点2的路径长度为2；
2）如果不存在路径，则输出No Path。如“1->2:No Path”。
样例输入
3,5
0,1,4
1,0,6
1,2,2
0,2,11
2,0,3
样例输出
0->1:4
0->2:6
1->0:5
1->2:2
2->0:3
2->1:7
刚才题目有点小错误，再次修正一下

什么是可耻的百度了一下啊？

别灰心，看一下离散或者数据结构的教学视频会有一些帮助的！说实话，如果叫我自学数据结构的话我也会崩溃的！有个人教的话好的多！

http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html
这里讲的Floyd 算法还比较清晰，大家可以看一看！

只不过语言是C++

如果存在路径 是指存在最短路径
1->2:2 是1至2的 最短路径上各边 权值之和为2！

书上的确是有，可是你能保证你敲出的程序，能按我的题目的要求输出正确的答案吗？理论和实际是不同的！

严蔚敏写的真是不太容易懂，在某些地方简直不知道他在说什么!我记得看那个子串位置的定位函数kmp算法足足看了七八个小时，才勉强看懂，够坑爹的！不过书写的的确很好，那种分函数的思想，宏定义的应用，指针的技巧。。。这完全是在实战开发，起点高了些！

算了，明天发答案吧！

#include <stdio.h>#include<string.h>
#define MAX_NAME 5 typedef int VRType;/*宏定义*/
#define OK 1 #define FALSE 0 #define TRUE 1
#define INFINITY 100000 #define MAX_VERTEX_NUM 20
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum; }MGraph;/*定义一个结构体数组，包括记录权值的邻接矩阵数组，总顶点数，以及初始的弧的数目*/
int CreateDN(MGraph *G)/*构建该结构体的函数*/
{
int i,j,k,b;
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);/*要求输入顶点数，以及弧的数目*/
for(i=0;i<(*G).vexnum;++i)
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j]=INFINITY;/*首先在邻接矩阵内置最大值即+∞，这里的+∞用一个较大的值代替*/
}
for(k=0;k<(*G).arcnum;k++)
{
scanf("%d,%d,%d",&i,&j,&b); /*输入arcnum个弧的信息，起点，终点，以及权值*/
(*G).arcs[i][j]=b;
}
return OK;
}
void ShortestPath_FLOYD(MGraph G,DistancMatrix *D)/*FLOYD算法*/
{
int u,v,w;
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
(*D)[v][w]=G.arcs[v][w];/*将结构体内邻接矩阵的信息记入D数组*/
}
for(u=0;u<G.vexnum;u++)/*这才是FLOYD算法的精华部分*/
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])
{
(*D)[v][w]=(*D)[v][u]+(*D)[u][w];
}
}
int main()
{
MGraph g;
int i,j;
DistancMatrix d;
CreateDN(&g);
for(i=0;i<g.vexnum;i++)/*邻接矩阵对角线元素为0*/
g.arcs[i][i]=0;
ShortestPath_FLOYD(g,&d);
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
{
if(i==j)
j++;
if(j>=g.vexnum)
break;
if(d[i][j]==100000)
printf("%d->%d:No Path\n",i,j);
else
printf("%d->%d:%d\n",i,j,d[i][j]);
}
return 0;
}

#include <stdio.h>
#include<string.h>
#define MAX_NAME 5
typedef int VRType;/*宏定义*/
#define OK 1
#define FALSE 0
#define TRUE 1
#define INFINITY 100000
#define MAX_VERTEX_NUM 20
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum; }MGraph;/*定义一个结构体数组，包括记录权值的邻接矩阵数组，总顶点数，以及初始的弧的数目*/
int CreateDN(MGraph *G)/*构建该结构体的函数*/
{
int i,j,k,b;
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);/*要求输入顶点数，以及弧的数目*/
for(i=0;i<(*G).vexnum;++i)
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j]=INFINITY;/*首先在邻接矩阵内置最大值即+∞，这里的+∞用一个较大的值代替*/
}
for(k=0;k<(*G).arcnum;k++)
{
scanf("%d,%d,%d",&i,&j,&b); /*输入arcnum个弧的信息，起点，终点，以及权值*/
(*G).arcs[i][j]=b;
}
return OK;
}
void ShortestPath_FLOYD(MGraph G,DistancMatrix *D)/*FLOYD算法*/
{
int u,v,w;
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
(*D)[v][w]=G.arcs[v][w];/*将结构体内邻接矩阵的信息记入D数组*/
}
for(u=0;u<G.vexnum;u++)/*这才是FLOYD算法的精华部分*/
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])
{
(*D)[v][w]=(*D)[v][u]+(*D)[u][w];
}
}
int main()
{
MGraph g;
int i,j;
DistancMatrix d;
CreateDN(&g);
for(i=0;i<g.vexnum;i++)/*邻接矩阵对角线元素为0*/
g.arcs[i][i]=0;
ShortestPath_FLOYD(g,&d);
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
{
if(i==j)
j++;
if(j>=g.vexnum)
break;
if(d[i][j]==100000)
printf("%d->%d:No Path\n",i,j);
else
printf("%d->%d:%d\n",i,j,d[i][j]);
}
return 0;
}

我总不能等你看完再发吧