关于图的最短路径算法实现的有关问题，帮帮忙~
关于图的最短路径算法实现的问题，帮帮忙~~
物电的同学让我给他做个程序，实现三个点（其实可以n个，简化了一下）最短路径查找，最短路径长度的输出，我看严蔚敏的《数据结构》p191上的算法，用c语言数组矩阵的方式存储图，简化了程序，但是不知道怎么实现不了……郁闷……谁能帮帮我啊~~~谢谢啦！！！
编的比较乱，包含了c++的用法，见谅……
代码如下：
#include<iostream>
#include<cstdlib>
#define INFINITY 1000//以一千代表无穷远
#define MAX_VERTEX_NUM 3//三个点，可以多个
typedef struct ArcCell{
int adj;//距离
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
AdjMatrix arcs;
}MGraph;//图
using namespace std;
int main(void){
MGraph G;//定义图
int i,v1,v2,w,j;
cout<<"now intiate the graph"<<endl;
for(i=0;i<MAX_VERTEX_NUM;++i)//初始化图的各点距离
for(j=0;j<MAX_VERTEX_NUM;++j)
G.arcs[i][j].adj=INFINITY;
cout<<"now take in every vexter's information"<<endl;
int flage=1;
for(int k=0;flage&&(k<MAX_VERTEX_NUM*MAX_VERTEX_NUM);++k)//输入相连点的距离
{
cout<<"take in v1 v2 w"<<endl;
cin>>v1>>v2>>w;
G.arcs[v1][v2].adj=w;
cout<<"if you haven't any more member to take in 0"<<endl;
cin>>flage;
}
cout<<" good luck!! we can do it!!"<<endl;
cout<<"it's you graph:";
for(int i=0;i<MAX_VERTEX_NUM;i++)//输出图
{cout<<endl;
for(int j=0;j<MAX_VERTEX_NUM;j++)
cout<<G.arcs[i][j].adj<<" ";}
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]={0};
cout<<endl;
cout<<"ok?"<<endl;
int v,u;
for(v=0;v<MAX_VERTEX_NUM;++v)//给图复值
for(w=0;w<MAX_VERTEX_NUM;++w)
D[v][w]=G.arcs[v][w].adj;
for(v=0;v<MAX_VERTEX_NUM;++v)
{
for(w=0;w<MAX_VERTEX_NUM;++w)
{if(D[v][w]<(INFINITY))//从v到w有直接路径
{
P[v][w][v]=1;
P[v][w][w]=1;
}
cout<<P[v][w][v];}
cout<<endl;}
cout<<"ok!"<<endl;
for(u=0;u<MAX_VERTEX_NUM;++u)//从这个最关键的地方卡壳了……
for(v=0;v<MAX_VERTEX_NUM;++v)
for(w=0;w<MAX_VERTEX_NUM;++w)
if(D[v][u]+D[u][w]<D[v][w])//从v经u有更短路径
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<MAX_VERTEX_NUM;i++)
P[v][w][i]=(P[v][u][i]||P[u][w][i]);
}//if
for(i=0;i<MAX_VERTEX_NUM;i++)//输出图中各点最短路径
for(j=0;j<MAX_VERTEX_NUM;j++)
{cout<<endl;
cout<<i<<"---"<<j<<":";
for(int k=0;k<MAX_VERTEX_NUM;k++){
if(P[i][j][k])
continue;
cout<<k;
}
}
cout<<endl;
cin>>i;
return 0;
}
会的帮帮忙吧~~谢谢啦！！
------解决方案--------------------
到我的资源下载里看看，里面资料丰富，包有你要的……
物电的同学让我给他做个程序，实现三个点（其实可以n个，简化了一下）最短路径查找，最短路径长度的输出，我看严蔚敏的《数据结构》p191上的算法，用c语言数组矩阵的方式存储图，简化了程序，但是不知道怎么实现不了……郁闷……谁能帮帮我啊~~~谢谢啦！！！
编的比较乱，包含了c++的用法，见谅……
代码如下：
#include<iostream>
#include<cstdlib>
#define INFINITY 1000//以一千代表无穷远
#define MAX_VERTEX_NUM 3//三个点，可以多个
typedef struct ArcCell{
int adj;//距离
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
AdjMatrix arcs;
}MGraph;//图
using namespace std;
int main(void){
MGraph G;//定义图
int i,v1,v2,w,j;
cout<<"now intiate the graph"<<endl;
for(i=0;i<MAX_VERTEX_NUM;++i)//初始化图的各点距离
for(j=0;j<MAX_VERTEX_NUM;++j)
G.arcs[i][j].adj=INFINITY;
cout<<"now take in every vexter's information"<<endl;
int flage=1;
for(int k=0;flage&&(k<MAX_VERTEX_NUM*MAX_VERTEX_NUM);++k)//输入相连点的距离
{
cout<<"take in v1 v2 w"<<endl;
cin>>v1>>v2>>w;
G.arcs[v1][v2].adj=w;
cout<<"if you haven't any more member to take in 0"<<endl;
cin>>flage;
}
cout<<" good luck!! we can do it!!"<<endl;
cout<<"it's you graph:";
for(int i=0;i<MAX_VERTEX_NUM;i++)//输出图
{cout<<endl;
for(int j=0;j<MAX_VERTEX_NUM;j++)
cout<<G.arcs[i][j].adj<<" ";}
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]={0};
cout<<endl;
cout<<"ok?"<<endl;
int v,u;
for(v=0;v<MAX_VERTEX_NUM;++v)//给图复值
for(w=0;w<MAX_VERTEX_NUM;++w)
D[v][w]=G.arcs[v][w].adj;
for(v=0;v<MAX_VERTEX_NUM;++v)
{
for(w=0;w<MAX_VERTEX_NUM;++w)
{if(D[v][w]<(INFINITY))//从v到w有直接路径
{
P[v][w][v]=1;
P[v][w][w]=1;
}
cout<<P[v][w][v];}
cout<<endl;}
cout<<"ok!"<<endl;
for(u=0;u<MAX_VERTEX_NUM;++u)//从这个最关键的地方卡壳了……
for(v=0;v<MAX_VERTEX_NUM;++v)
for(w=0;w<MAX_VERTEX_NUM;++w)
if(D[v][u]+D[u][w]<D[v][w])//从v经u有更短路径
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<MAX_VERTEX_NUM;i++)
P[v][w][i]=(P[v][u][i]||P[u][w][i]);
}//if
for(i=0;i<MAX_VERTEX_NUM;i++)//输出图中各点最短路径
for(j=0;j<MAX_VERTEX_NUM;j++)
{cout<<endl;
cout<<i<<"---"<<j<<":";
for(int k=0;k<MAX_VERTEX_NUM;k++){
if(P[i][j][k])
continue;
cout<<k;
}
}
cout<<endl;
cin>>i;
return 0;
}
会的帮帮忙吧~~谢谢啦！！
------解决方案--------------------
到我的资源下载里看看，里面资料丰富，包有你要的……