数据结构上机报告

数据结构上机报告

课程：有向图中求各顶点之间的最短路径

算法设计：

现设一个矩阵F，用来记录路径长度。初始时，顶点Vi到顶点Vj的最短路径长度F[i][j]=weight[i][j],即弧上的权值。若不存在,则F[][]=∞（程序中用1000表示）。此时，把矩阵F记做F0。F0考虑到了有弧相连直接到达的路径，但这个长度不是最短长度，所以要进行探索。

① 让路径经过V0（第一个顶点），并比较路径（Vi,Vj）和路径（Vi,V0,Vj）的长度，去较短的作为最短路径长度。其中，路径（Vi,V0,Vj）的长度等于路径（Vi,V0）和（V0,Vj）长度之和，即F[i][j]=F[i][0]+F[0][j]。把此时得到的矩阵F记做F1，F1考虑到了各项点间除直接到达的路径外，其他经过V0的路径，只取其中最短的作为最短路径长度。

② 在F1的基础上让路径经过第二个顶点V1，依照?的方法求得最短路径长度，得到F2。

③ 以此类推，经过n次试探，将n个顶点都考虑到路径之中，此时求得最短路径长度。

例：有向图如下：

求任意两个顶点之间的最短路径长度

程序运行如下：

程序代码：

#include using namespace std;

#define MAXVEW 10 //定义顶点个数 typedef int weight; //定义权值

typedef struct //定义结构 {

weight arcs[MAXVEW][MAXVEW]; char data[MAXVEW]; int vexs;

}MGraph,*AdjMetrix;

void CreateGraph(AdjMetrix g,int n) //构建图及其邻接矩阵 {

cout<<\请按提示输入顶点信息及其之间的权值，注意若两顶点之间无路径，则权值无穷大，用1000表示\\n\ int i,j; g->vexs=n;

for(i=0; i

cout<<\请输入第\个顶点的信息：\ cin>>g->data[i];

cout<<\请输入该顶点和其它顶点之间的权值：\ for(j=0; j

cin>>g->arcs[i][j]; cout<<'\\n'; } }

void DispGraph(AdjMetrix g) //显示邻接矩阵 {

int i,j;

cout<<\顶点及邻接矩阵:\\n\ for(i=0; ivexs; i++) cout<<'\\t'<data[i]; cout<<'\\n';

for(i=0; ivexs; i++) {

cout<data[i]<<'\\t'; for(j=0; jvexs; j++)

cout<arcs[i][j]<<'\\t'; cout<<'\\n'; }

cout<<'\\n\\n';

}

void Floyd(AdjMetrix g) //采用Floyd法计算各顶点之间的最短路径，可计算有向图及无向图 {

int path[MAXVEW][MAXVEW]; int F[MAXVEW][MAXVEW]; int i,j,k;

for(i=0; ivexs; i++)

for(j=0; jvexs; j++) {

F[i][j]=g->arcs[i][j]; path[i][j]=-1; }

for(k=0; kvexs; k++) for(i=0; ivexs; i++) for(j=0; jvexs;j++) if( F[i][j]>F[i][k]+F[k][j]) {

F[i][j]=F[i][k]+F[k][j]; path[i][j]=k; }

cout<<\每对顶点间最短路径为:\\n\for(i=0; ivexs; i++) { for(j=0; jvexs;j++) if(F[i][j]!=1000&&i!=j) {

cout<data[i]<<\

cout<data[j]<<'\\t'<

} }

void main() {

MGraph gg; AdjMetrix g=≫ int n;

cout<<\请输入顶点个数： cin>>n;

CreateGraph(g,n); DispGraph(g); Floyd(g); }

\

本文来源：https://www.bwwdw.com/article/iy6r.html