鄰接矩陣存儲(chǔ)法和Floyd算法求解任意兩個(gè)頂點(diǎn)的最短路徑數(shù)據(jù)結(jié)構(gòu)報(bào)告

1、-. z數(shù)據(jù)構(gòu)造上機(jī)報(bào)告2)：可心*：班級(jí)：1403018題目描述一個(gè)圖的存儲(chǔ)矩陣如下所示頂點(diǎn)分別是0、1、2、3、4、5：0， 12， 18， ， 17， 12, 0， 10， 3， ， 518，10， 0， ， 21， 11， 3， ， 0， ， 817， ， 21， ， 0， 16， 5， 11， 8， 16， 0試用鄰接矩陣存儲(chǔ)法和Floyd算法求解任意兩個(gè)頂點(diǎn)的最短路徑。輸入：輸入數(shù)據(jù)第一行為1個(gè)正整：頂點(diǎn)個(gè)數(shù)n(頂點(diǎn)將分別按0，1，n-1進(jìn)展編號(hào))。后面有n+1行，前n行都有n個(gè)整數(shù)第i行第j個(gè)數(shù)表示頂點(diǎn)i-1和頂點(diǎn)j-1之間的邊長(zhǎng)，用10000來表示兩個(gè)頂點(diǎn)之間無邊；第n+1行輸

2、入一對(duì)頂點(diǎn)*和y輸出：*和y頂點(diǎn)的最短路徑長(zhǎng)度和最短路徑(路徑換行輸出，只輸出頂點(diǎn)編號(hào)序列)。例如輸入1：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 00 1例如輸出1：1201例如輸入2：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 16100

3、00 5 11 8 16 02 3例如輸出2：13213例如輸入3：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 01 4例如輸出3：21154例如輸入in和out文件的容：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8

4、 16 03 4例如輸出：24354解題思路先用鄰接矩陣存儲(chǔ)法構(gòu)建矩陣輸入，分別輸入頂點(diǎn)數(shù)，路徑長(zhǎng)度矩陣，鄰接矩陣，再通過Floyd算法求解任意兩個(gè)頂點(diǎn)的最短路徑，具體代碼如下。源代碼#include#includeint main()int n,i,j,k,a,b,ne*t;printf(請(qǐng)輸入頂點(diǎn)數(shù)：n);scanf(%d,&n);int Gnn;/輸入鄰接矩陣int Dnn;/路徑長(zhǎng)度矩陣int Pnn;/路徑矩陣指向頭結(jié)點(diǎn)的后繼路徑如果是abc,則Pac=b Pbc=cprintf(請(qǐng)輸入鄰接矩陣：n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&Gij);Dij=Gij;Pij=j;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jDik+Dkj)Dij=Dik+Dkj;Pij=Pik;scanf(%d %d,&a,&b);if(Dab=10000)printf(a和b之間無路徑n);elseprintf(%dn,Dab);printf(%d,a);for(