for(j=0;j<G->n;j++)
{
if(i!=j)
{
cout<<" "<<i<<"->"<<j<<";";
if(A[i][j]==INF)
{
if(i!=j)
cout<<"不存在路径"<<"\n"<<endl;
}
else
{
cout<<"路径长度为:"<<A[i][j]<<"\n";
cout<<"路径为:"<<i<<"*";
有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难，经过分析这两个值可以合并为一个权值即distance*frequency；这样就使得图的建立轻而易举。
5.2本题目的关键点之二：
利用floyd算法求出每一对顶点之间的最短路径。
5.3本题目的关键点之三：
选出最短路径，即最佳地点应使其到其他单位权值最小。注意：每比较一次path应清0一次（Path=0）。
k=i;
}
cout<<"超市的最佳地址为:"<<G->vexs[k]<<endl;
}
voidmain()
{
Mgraph *Gh=NULL;
Gh=(Mgraph *)malloc(sizeof(Mgraph));
CreatMgraph(Gh);
Floyed(Gh);
system("pause");
}
/*测试数据：
if(G->adj[i][j]==0&&i!=j)
G->dis[i][j]=INF;
}
}
void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
int count[MAXVEX];
学以致用，这才是我的目标，课程设计给了我这个机会。数据结构是计算机科学与技术专业的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。
for(j=0;j<G->n;j++)
if(A[i][j]>(A[i][k]+A[k][j])) //从i经j到k的一条路径更短
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
cout<<endl<<"Floyed算法求解如下:"<<endl;
for(i=0;i<G->n;i++)
6 测试结果
6.1输入
6.2输出
总 结
数据结构课程设计完成了，对我来说这是一项小小的挑战，它不仅检验了我的学习情况，也考验了我的意志力，收获非颇丰！
通过一学期的学习，我知道数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。
pre=path[i][j];
while(pre!=-1)
{
cout<<pre<<"\n";
pre=path[pre][j];
}
cout<<j<<endl;
}
}
}
//以下为选择总体最优过程，然后确址；
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
{
if(A[i][j]==INF)
scanf("%s",&G->vexs[i]);
}
for(i=0;i<G->n;i++)//结构体的初始化；
for(j=0;j<G->n;j++)
{
G->adj[i][j]=0;
G->dis[i][j]=0;
G->f[i]=0;
}
for(k=0;k<G->e;k++)
{
printf("请输入相通的两单位(输入格式:i,j):\n");
输入：
单位个数
4
单位间的路径数
6
第0个单位名称
a
第1个单位名称
b
第2个单位名称
c
第3个单位名称
d
相通两单位之间的距离
0,1 3
1,2 2
2,3 2
0,3 3
0,2 4
1,3 1
第0个单位去超市的频率1
第1个单位去超市的频率2
第2个单位去超市的频率4
第3个单位去超市的频率3
5调试分析
5.1本题目的关键点之一：
2 运行环境
Visual Stdio C++6.0
Windows Vista/2003/XP
3 概要设计
Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=(V, E, w)是一个带权有向图，其边V={v1, v2, …, vn}。对于k≤n，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：
count[i]=0;
else
count[i]=1;
}
for(i=0;i<G->n;i++)
if(count[i])
{
for(j=0;j<G->n;j++)
if(i!=j)A[i][i]+=A[j][i];
}
k=0;
for(i=0;i<G->n;i++)
{
if(count[i])
if(A[k][k]>A[i][i])
通过数据结构课程实践，加上老师的全力指导，无论是理论知识，还是实践动手能力，我都有了不同程度上的提高。
scanf("%d,%d",&i,&j);//在距离上体现为无向；
printf("请输入相同两个单位间的距离(格式：dis)：\n");
scanf("%d",&(G->dis[i][j]));
G->adj[i][j]=1;
G->adj[j][i]=1;
G->dis[j][i]=G->dis[i][j];
课程设计报告
课程设计题目：学校超市选址
学生姓名：杨婕
专业：软件工程
班 级：091115
学 号：09111530
指导教师：许志文
2011年6月15日
1 需求分析
核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)
数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)
存储结构: typedef struct
}
for(k=0;k<G->n;k++)
{
printf("请输入第%d个单位去超市的相对频率:\n",k);
scanf("%d",&(G->f[k]));
}
for(i=0;i<G->n;i++)//以距离和频率之积作为权值；
for(j=0;j<G->n;j++)
{
G->dis[i][j]*=G->f[i]; //最终权值非完全无向；
{
string vexs[MAX_VERTLeabharlann BaiduX_SIZE];
int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
int vexnum;// ,arcnum;
}MGraph;
核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)
输入数据: 各单位名称，距离，频度，单位个数．
原问题转化为对每个i和j求，或者说求矩阵
流程图
4详细设计
第一步，让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-1），A（n-1）即所求结果。A（n-1）[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)[i][j]表示从i到j的最短路径长度。
for(i=0;i<G->n;i++) //初始化A[][]和path[][]数组
for(j=0;j<G->n;j++) //置初值；
{
A[i][j]=G->dis[i][j];
path[i][j]=-1;
count[i]=0;
}
for(k=0;k<G->n;k++) //k代表运算步骤
{
for(i=0;i<G->n;i++)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "malloc.h"
#include <iostream.h>
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
输出数据: 所选单位名称．
总体思路: 如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。
假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。
int dis[MAXVEX][MAXVEX];//单位间距离（边的长度）；
int f[MAXVEX];//各单位去超市的频率；
int n;//顶点数和边数；
int e;
}Mgraph;#include <string.h>
void CreatMgraph(Mgraph *G)
{
int i,j,k;
printf("请输入单位个数:\n");
scanf("%d",&(G->n));
printf("请输入单位间的路径数:\n");
scanf("%d",&(G->e));
printf("请输入单位名称:\n");
for(i=0;i<G->n;i++)
{
printf("请输入第%d个单位名称:\n",i);
#define OVERFLOW -1
#define INF 32767
const int MAXVEX=100;
typedef char Vextype;
typedef struct
{
Vextype vexs[MAXVEX][MAXVEX]; //单位名称（顶点信息）；
int adj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；
