大连公共汽车车体广告:急求数据结构课程设计（要求原创）

最短路径：
const MaxValue = 200; //最大值 max
typedef struct edge{
int fromvex;
int endvex;
float weight;
}edge,edgeset[MaxEdge]; //定义边
int LocateVex(char v,char GV[],int n)
{ //寻找某顶点的位置
int i;
for (i = 0; i < n; i++)
if (v == GV[i]) break;
return i;
}
void Prim(float GA[][MaxVertex], edgeset CT,int a ,int n) //用Prim算法构建最小路径
{ //将最小路径保存在数组CT[n-1]中
int i,j,k,t,m;
float min,w;
for (i = 0; i < n; i++)
{
if (i <a)
{
CT[i].fromvex = a;
CT[i].endvex = i;
CT[i].weight = GA[a][i];
}
else if (i>a)
{
CT[i-1].fromvex = a;
CT[i-1].endvex = i;
CT[i-1].weight = GA[a][i];
} //付初值，CT中有n-1个值
}
for (k=1;k<n;k++)
{
min = MaxValue;
m = k-1;
for (j=k-1;j<n-1;j++)
if (CT[j].weight<min)
{
min = CT[j].weight;
m = j;
}
edge temp = CT[k-1]; //确保前k-1是已经找好的路径
CT[k-1] = CT[m];
CT[m] = temp;
j = CT[k-1].endvex;
for (i=k;i<n-1;i++)
{
t = CT[i].endvex;
w = GA[j][t];
if (w < CT[i].weight)
{
CT[i].weight = w;
CT[i].fromvex = j;
}//if
}//for修改一个集合到另一集合的最短路径
}//for
}//Prim
/**********************************************
*
**********************************************/
void main()
{
edgeset CT;
char GV[MaxVertex]; //顶点描述
float GA[MaxVertex][MaxVertex];//邻接矩阵
char v1,v2,ch;
int n,e;
int i,j,k;
float w;
cout << "输入街区总数:";
cin >> n;
cout <<"输入"<<n<<"个街区的代号："<<endl;
for (i = 0; i < n; i++)
cin >> GV[i];
for (i = 0; i<n; i++)
for (j=0;j<n;j++)
{
if (i==j)
GA[i][j]=0;
else GA[i][j]=MaxValue;
} //邻接矩阵付初值
cout <<"规划铺设的管道总数: ";
cin >>e;
cout <<"输入准备铺设管道的两街区及其所需经费: "<<endl;
for (k=1;k<=e;k++)
{
cout <<"两街道:";
cin >>v1;
cin >>v2;
cout <<"经费:";
cin >>w;
i = LocateVex(v1,GV,n);
j = LocateVex(v2,GV,n);
GA[i][j] = GA[j][i] = w;
}
cout <<"请任意输入准备最先考虑的街区号: "<<endl;
cin >>ch;
i = LocateVex(ch,GV,n);
Prim(GA,CT,i,n);
cout <<"最短路径:"<<endl;
for (i = 0; i < n-1; i++)
cout << '(' << GV[CT[i].fromvex] << ',' << GV[CT[i].endvex] << ')' << CT[i].weight <<endl;
}

当年我们也是做这啊。