C语言高手！！帮忙写个最短路径程序！！！！

Question

要大图的可发至邮箱！！！ 谢谢啦！！！
我是真的一点都不会做才来问的！！！
麻烦给个完整的答案！！！

Answer 1

这是我们的一个实验，你可以参考一下
一、 需求分析
【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】
（1） 设计你所有学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2） 为来访客人提供图中任意景点相关信息的查询。
（3） 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
【测试数据】
由读者根据实际情况指定。
二、概要设计
本次实验中运用到的数据类型有：图，顶点，边结点
typedef struct edgenode
{
int adjvex; //临接点序号
int length; //道路长度
char name[20]; //景点名称
char info[100]; //景点详细信息
struct edgenode *next;
}edgenode, *Node ;
typedef struct
{
char data[20]; //存储景点的名称.
char str[100]; //具体的介绍此景点
struct edgenode *link; //指向下一个景点
}vexnode; //景点及其信息.
typedef struct Edge
{
int lengh; //边的权值，表示路径长度.
int ivex, jvex; //边的两端顶点号
struct Edge *next; //指向下一条边
} EdgeType; //边及其信息.
typedef struct
{
int num; //顶点编号
char data[20]; //顶点名称
} vertex;
typedef struct{
vertex vexs[MAX]; //顶点集合
int edges[MAX][MAX]; //邻接矩阵
}adjmax;
基本操作：
void fun();
//操作结果：功能说明并显示所有景点
void creatgraph(vexnode g[],int &n, EdgeType e[],adjmax &adj);
//操作结果：创建校园图
void travgraph(vexnode g[],int n,adjmax adj);
//初始条件：已知邻接表adj和顶点g及其数目n
//操作结果：查找指定景点信息
void Ppath(int path[][MAX],int i,int j,vexnode g[]);
//操作结果：寻找最短路径
void Dispath(int A[][MAX],int path[][MAX],int n,vexnode g[]);
//初始条件：已知顶点g和数目n及其权值
//操作结果：显示最短路径
void Floyd(adjmax adj,int n,vexnode g[]);
//初始条件：已知邻接表adj和顶点g
//操作结果：Floyd算法计算所有两个景点间最短路径
三、详细设计
1、---------main()---------
char choice;
int n = 0; / /景点数目
vexnode g[MAX]; //保存顶点及其信息
EdgeType e[MAXedg]; //保存边及其信息
adjmax adj; //保存边和定点

creatgraph(g,n,e,adj); //建立校园导游图
while(1)
{
do{
system("cls");
fun(); //功能说明
printf("请输入所要进行的操作：");
choice=getch();
printf("\n"); }while(choice!='s'&&choice!='S'&&choice!='v'&&choice!='V'&&choice!='Q'&&choice!='q');
switch(choice)
{
case('s'):
case('S'): Floyd(adj,n,g); //查找最短路径
break;
case('v'):
case('V'):travgraph(g,n,adj); //景点查询
break;
case('q'):
case('Q'):return; //结束程序
}
}
2、------- travgraph()---------
void travgraph(vexnode g[],int n,adjmax adj)
{
int i = 1,flag = 1,num; //num存储要查询的景点的序号
char ch;
edgenode *p;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&num);
while(i <= n) //遍历邻接表
{
p = g[i].link;
if(i == num && flag == 1)
{
printf("此景点的名称是: %s\n",g[i].data);
printf("此景点的介绍是: %s\n",g[i].str);
printf("是否继续? Y/N");
ch=getch();
printf("\n");
if(ch == 'Y' || ch == 'y') //继续
{
flag = 1;
i = 1;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&num);
getchar();
}
else
flag = 0; //不继续
}
else
i++;
}
}3、------- Floyd()---------
//Floyd算法计算所有两个景点间最短路径
void Floyd(adjmax adj,int n,vexnode g[])
{
int A[MAX][MAX],path[MAX][MAX]; //A是路径长度，path是路径。
int i,j,k;
for(i = 1; i <= n; i++) //初始化
for(j = 1; j <= n; j++)
{
A[i][j] = adj.edges[i][j]; //i j之间长度
if(i == j)
{
A[i][j] = 0;
}
path[i][j] = -1; //初始化
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k]+A[k][j]; //修改最短路径长度值
path[i][j] = k; //将最短路径的节点号保存
}
}
Dispath(A,path,n,g); //用户输入，查找任意两个景点间的最短路径。
}

Answer 2

一、Dijkstra（效率O(n^2)）【这个不会的话，我有一个flash，可以发给你】
for(int k=1;k<=n-1;k++)
{
int p,min=INF;
for(int i=1;i<=n;i++)//找出非最优值的点的最小值
if(!v[i] && min>d[i])
{
min=dist[i];p=i;
}
if(min==INF)break;//无解或不连通
v[p]=1;
for(int i=1;i<=n;i++)
dist[i]<?=dist[p]+g[p][i];
}
cout<<d[n]<<endl;

二、SPFA（效率O(ke)k表示一个不大于2的常数，e表示边的条数）【目前认为是最快的！！】
head=tail=0;
memset(v,0,sizeof(v));
v[1]=q[++t]=1;//用循环队列来记录要更新的点
while(head!=tail)
{
int k=q[++(head%=n)];
v[k]=1;//用v数组标记是否入队
for(int i=1;i<=n;i++)
if(dist[i]>dist[k]+g[i][k])//dist[i]表示第i点到源点的距离，g[i][j]表示i到j的距离
{
dist[i]=dist[k]+g[i][k];
if(!v[i])//如果没入队，就入队
{
q[++(tail%=n)]=i;
v[i]=0;
}
}
}

三、floyed（效率O(n^3)，不过这个可以求出所有点与点之间的最短路）
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]<?=g[i][k]+g[k][j];

Answer 3

这个题目数据结构书上有答案，不过我忘了 ，留个爪印，我不得不说你几句，你自己书上现成的代码，组织一下变成C语言你都不肯，真懒