数据结构域算法设计-143 【图论基础】求一个无向图的最短路径(dijkstra) 144 有向图中任意两点最短路径(floyd) 教案

《数据结构域算法设计-143 【图论基础】求一个无向图的最短路径(dijkstra) 144 有向图中任意两点最短路径(floyd) 教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【图论基础】求一个无向图的最短路径（dijkstra）TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:112Accepted:46Description　　一个含n个结点的无向图，以矩阵存储方式给出，请求出指定的两个点之间的最短距离。Input　　第一行，一个整数n（0

2、j。表示求解i点到j点的最短距离。Output　　一个数值，表示指定的两点之间最短距离。SampleInput2022012SampleOutput2Source·var·i,j,k,n,min:longint;·x,y:longint;·a:array[1..1000,1..1000]oflongint;·b:array[1..1000]oflongint;·c:array[1..1000]ofboolean;·begin·readln(n);·fori:=1tondo·forj:=1tondoread(a[i,

3、j]);·readln(x,y);·fillchar(c,sizeof(c),0);·fillchar(b,sizeof(b),$7);·k:=x;b[x]:=0;·fori:=1ton-1dobegin·c[k]:=true;·forj:=1tondo·if(a[k,j]<>0)andnotc[j]and(a[k,j]+b[k]

4、n·min:=b[j];k:=j;·end;·end;·writeln(b[y]);·end.【图论基础】有向图中任意两点最短路径（floyd）TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:69Accepted:35Description　　一个含n个结点的有向图（注意：是有向图！！），以矩阵存储方式给出，请求出指定的多组两个点之间的最短距离及其最短路径。Input　　第1行，一个整数n（0

5、*n的矩阵，表示无向图中各结点之间的联结情况，矩阵中的数据为小于1000的正整数，其中-1表示无穷大！！　　第（n+2）行，一个整数m，表示接下来有m组顶点对，其中，i是起点，j是终点，且i不等于j。　　接下来有m行，每行两个整数，中间一个空格间隔，分别表示i和j，表示求解i点到j点的最短距离及最短路径。　　注：输入数据已经确保答案每一组顶点间的最短路径是唯一的，无多解数据存在，顶点编号用数字表示，从1开始编号，至n结束！Output　　共2m行。　　第(m-1)*2+1行，一个整数，表示第m组顶点的最短

6、距离，若两点间距离为无穷大，则输出-1。　　第(m-1)*2+2行，用顶点编号表示的路径序列，各顶点编号间用一个空格间隔，表示第m组顶点的最短路径，若两点间距离为无穷大，则输出的路径序列为-1。SampleInput304116023-1022132SampleOutput52317312Source虽然我不会用floyd写，但这还是一种方法~~~·var·i,j,k,z,n,m,x,y,min:longint;·a:array[1..300,1..300]oflongint;·d,f:array[1..300]o

7、flongint;·e:array[1..300]ofboolean;·proceduredfs(y:longint);·begin·iff[y]<>0thendfs(f[y]);·write(y,'');·end;··begin·readln(n);·fori:=1tondo·forj:=1tondoread(a[i,j]);·readln(m);·forz:=1tomdobegin·readln(x,y);·fillchar(d,sizeof(d),$7);·fillchar(e,sizeof(e),0);·f

8、illchar(f,sizeof(f),0);·k:=x;d[x]:=0;·fori:=1ton-1dobegin·e[k]:=true;·forj:=1tondoifa[k,j]>0then·if(d[k]+a[k,j]