2023年數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告最短路徑

實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)名稱短途徑

課程名稱數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)

專業(yè)班級(jí)：信息安全

學(xué)號(hào)：

姓名：

實(shí)驗(yàn)六最短途徑

一、實(shí)驗(yàn)?zāi)康?/p>

1.學(xué)習(xí)掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)

2.學(xué)會(huì)編寫(xiě)求最短途徑的算法

二、實(shí)驗(yàn)內(nèi)容

1、實(shí)驗(yàn)題目

編寫(xiě)代碼實(shí)現(xiàn)Dijkstra生成最短途徑的算法，其中要有完整的圖的輸入輸出

2、簡(jiǎn)樸介紹

圖的存儲(chǔ):用鄰接矩陣，這樣會(huì)方便不少。

鄰接矩陣是一個(gè)二維數(shù)組，數(shù)組中的元素是邊的權(quán)（一些數(shù)值），數(shù)組下標(biāo)號(hào)為結(jié)點(diǎn)的標(biāo)號(hào)。

（1）例如二維數(shù)組中的一個(gè)元素M[5][6]的值為39,則表達(dá)結(jié)點(diǎn)5、6連接，且其上的權(quán)值

為39。

（2）用鄰接矩陣存儲(chǔ)圖，對(duì)圖的讀寫(xiě)就簡(jiǎn)樸了。由于鄰接矩陣就是一個(gè)二維數(shù)組，因此對(duì)圖的

讀寫(xiě)就是對(duì)二維數(shù)組的操作。只要能弄清楚邊的編號(hào)，就能把圖讀入了。

用一對(duì)結(jié)點(diǎn)表達(dá)邊（也就是輸入的時(shí)候輸入一對(duì)結(jié)點(diǎn)的編號(hào)）

求最短途徑的算法：

求最短途徑就是求圖中的每一個(gè)點(diǎn)到圖中某一個(gè)給定點(diǎn)（這里認(rèn)為是編號(hào)為0的點(diǎn)）的最短

距離。

具體算法就是初始有一個(gè)舊圖，一個(gè)新圖。開(kāi)始的時(shí)候舊圖中有所有的結(jié)點(diǎn)，新圖中初始為

只有一個(gè)結(jié)點(diǎn)（源點(diǎn)，途徑的源頭）。整個(gè)算法就是不斷的從舊圖中往新圖中添加點(diǎn)，直到所

有的點(diǎn)都添加到新圖中為止。

要實(shí)現(xiàn)這個(gè)算法，除了用二維數(shù)組保存圖，還需要使用到兩個(gè)輔助的數(shù)組

數(shù)組find[N]:此數(shù)組是用來(lái)表達(dá)標(biāo)號(hào)相應(yīng)的結(jié)點(diǎn)是否已經(jīng)被添加到新圖中（由于只有舊圖

中的點(diǎn)我們才需要添加到新圖中，并且只有舊圖中點(diǎn)到源點(diǎn)的距離，我們才需要進(jìn)行更新）

其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。

數(shù)組distance[N]:此數(shù)組記錄圖中的點(diǎn)到源點(diǎn)的距離。這個(gè)數(shù)組里面存放的值是不斷進(jìn)行

更新的。其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。

大的循環(huán)：逐一把舊圖中的所有點(diǎn)添加到新圖中.,

循環(huán)：遍歷distance數(shù)組，找distance數(shù)組中屬于舊圖中的點(diǎn)，其中

distance最小的那個(gè)結(jié)點(diǎn)

把找到的結(jié)點(diǎn)添加到新圖中.，

更新distance數(shù)組，因?yàn)樾绿砑恿艘粋€(gè)點(diǎn)到新圖中，所以可能能找到

一條通過(guò)這條點(diǎn)的新的路徑，這條路徑可能比原來(lái)的路徑更短.。

3、程序簡(jiǎn)樸模板

只是參考，不需要照著這個(gè)來(lái)寫(xiě)

〃最短途徑

#ifndefMYGRAPH_H_

#defineMYGRAPH_H_

classMyGraph

(

public:

ovoidreadDirectedGraph();

oMyGraph(intsize);//構(gòu)造函數(shù)中設(shè)立圖的大小，分派空間

avoidwriteGraph();

voidshortPath(intsource);〃求最短途徑

protected：

private:

“nt**m_graph；〃用二維數(shù)組保存圖

°intm_size;〃圖的大小

0

);

#endif

/////////////////////////////////////////////////////////////////////

〃構(gòu)造函數(shù)中設(shè)立圖的大小，分派空間

MyGraph:：MyGraph(intsize)

(

“nti,j;

m_size=size;

〃給圖分派空間

n)_graph=newint*[m_size];

ofor(i=0;i<m_size;i++)

°{

6m_graph[i]=newint[m_size]；

°}

ofor(i=0;i<m_size;i++)

(

?>fdr(j—0;j<m_size；j++)

00{

m_graph[i][j]=INT_MAX；

)

°}

三、實(shí)驗(yàn)代碼

#inc1ude<iostream>

#include<iomanip>

#inc1ude<stack>

#inelude<deque>

#inc1ude<fstream>

usingnamespacestd;

struetprimnode

(

public:

charbegvex;

charendvex;

intlowcost;

)；

structadknode

(

intdist;〃最近距離

charway[50]；//頂點(diǎn)數(shù)組

intnodenum；〃通過(guò)的頂點(diǎn)數(shù)

)；

classMgraph//鄰接矩陣儲(chǔ)存結(jié)構(gòu)

public：

Mgraph(){}

~Mgraph(){}

voidCreatMGraph();

voidDFS(int);〃用遞歸實(shí)現(xiàn)

voidDFSl(int)；//非遞歸

voidBFS(int);

voidprint();

voidprim();

intmini()；

int1ow();〃最短距離函數(shù)的輔助函數(shù)

intLocateVex(char);

voidkruskal();

voidDijkstra();

voidFloyd();

private:

intnumber;//頂點(diǎn)數(shù)目

intarcnum;//邊的數(shù)目

charvexs[50];

intarcs[50][50];

intvisited[50];//便利時(shí)的輔助工具

primnodecloseedge[50]；//prim

adknodedist[50];//最短途徑

intD[20][20];//floyd算法距離

intP[20][20][20]；//f1oyd算法途徑

}；

intMgraph::LocateVex(chars)

for(inti=0;i<number;i++)

if(vexs[i]==s)

returni；

return-1;

)

voidMgraph::print()

(

coutV〈”頂點(diǎn)為：”；

for(intk=0；k<number;k++)

cout?vexs[k];

cout<<end1；

for(inti=0；i<number;i++)

{

for(intj=0；j<number;j++)

cout<<setw(6)?left?arcs[i][j]?"n；

cout?end1；

)

fbr(intm=0;m<number；m++)

cout?visited[m];

cout?endl;

)

voidMgraph：：CreatMGraph()〃圖的鄰接矩陣儲(chǔ)存結(jié)構(gòu)

(

charvexl,vex2;

inti,j,k,m;

coutVv”請(qǐng)輸入定點(diǎn)數(shù)，邊數(shù):"v<endl;

cin>>number>>arcnum;

coutvv”請(qǐng)輸入頂點(diǎn)(字符串類型)：“<<endl;

for(i=0;i<number;i++)

cin>>vexs[i];

for(i=0;i<number；i++)

for(j=0;j<number;j++)

arcs[i]|j]=1000；

for(k=0;k<arcnum；k++)

(

cout?”請(qǐng)輸入邊的兩個(gè)頂點(diǎn)及邊的權(quán)值："<<end1;

cin>>vexl>>vex2?m;

i=LocateVex(vexl)；

j=LocateVex(vex2);

arcs[i][j]=m;

arcs[j][i]=m;

)

)

voidMgraph::DFS(inti=0)〃用遞歸實(shí)現(xiàn)

(

intj;

cout<<vexs[i]?M------>”；

visited[i]=1；

for(j=0;j<number;j++)

if(!(arcs[i][j]==1000)&&!visited[j])

DFS(j);

}

voidMgraph：:DFS1(inti=0)//非遞歸

stack<int>st;

st.push(i);

while(!st.empty())

(

intj=st.top();

St.pop();

cout<<vexs[j]?"---->";

visited[j]=1;

for(intk=0;k<number；k++)

(

if((!(arcs[j][k]==1000))&&!visitedLk])

st.push(k);

)

)

voidMgraph::BFS(inti=O)〃廣度優(yōu)先遍歷

(

deque<int>de；

de.push_back(i);

cout<<vexs[i]<<*'——--->**；

visitedfi]=1;

whi1e(!de.empty())

intk=de.front();

for(intj=0;j<number；j++)

(

if(arcs[k][j]!=1000&&!visited[j])

|

cout?vexs[j]?n-......

visited[j]=l;

de.push_back(j)；

)

)

de.pop_front()；

)

)

intMgraph:：mini()

(

staticinti;

intmin=0；

for(intj=0;j<number;j++)

(

if(!visited[j])

(

if(closeedge[min].lowcost>closeedge[j].lowcost)

min=j；

)

i=min;

cout<<"涉及邊("v<closeedge[i].begvex<closeedge[i].endvex<<M)u；

returni;

)

voidMgraph::prim()

(

charu;

cout<<”請(qǐng)輸入起始頂點(diǎn)："?endl;

cin?u;

inti=LocateVex(u);

visited[i]=1;

for(intj=0;j<number;j++)

(

c1oseedge[j].begvex=u;

closeedge[j].endvex=vexs[j]；

c1oseedge|j].lowcost=arcs[i][j];

)

for(intm=l;m<number;m++)

(

intn=mini();

visited[n]=l；

c1oseedge[nJ.lowcost=l000;

for(intp=0;p<number;p++)

if(!visited[p])

if(arcsLp][n]<closeedgelpj.lowcost)

(

closeedge[pj.lowcost=arcs[p][n];

closeedge[p].begvex=vexs[n];

)

)

)

)

)

voidMgraph:：kruska1()

(

inta,b,k=0;

intmin=l000；

intarcsl[20][20];

for(intm=0；m<number；m++)

visited[m]=m;〃每一個(gè)頂點(diǎn)屬于一顆樹(shù)

for(inti=0;i<number;i++)

for(intj=O;j<number;j++)

arcsl[i][j]=arcs[i]Lj];

whi1e(k<number-1)

{

min=1000;

for(inti=0；i<number;i++)

for(intj=0;j<number；j++)

if(arcsl[iJ[j]<min)

(

a=i；

b=j;

min=arcsl[ij[jj;

)

)

)

if(visited[a]!=visited[b])

{

cout<<"涉及邊<"?vexs[a]?","?vexs[b]?")";

k++;

for(intn=0;n<number;n++)

(

if(visited[n]==visited[b])

visited[n]=visited[a];

)

}

e1se

arcsl[a|[b]=arcs[b][a]=1000;

}

)

voidMgraph：:Dijkstra()

cout<<”請(qǐng)輸入起始點(diǎn)”<Vendl;

charu；

cin?u;

inti=LocateVex(u);

visited[i]=1；

for(intj=0；j<number;j++)

{

dist[j].dist=arcs[i][j];

dist[j].nodenum=0：

)

for(j=l；j<number;j++)

(

intdistance=1000；

intmin=0;

for(intn=0;n<number;n++)

(

if(!visited[n])

{

if(distance>dist[n].dist)

(

distance=dist[n].dist;

min=n：

intm=min;

visited[m]=1：

for(n=0;n<number；n++)

{

if(!visitedlnj)

(

if((dist[m].dist+arcs[m]LnJ)<dist[n].dist)

(

dist[n].dist=dist[m].dist+arcs[mj[n];

dist[n].nodenum=0;

for(intx=0;x<distLmJ.nodenum;x++)

(

dist[n].way[x]=dist[m].way[x];

dist[n].nodenum++；

)

dist[n].way[dist[n].nodenum++]=vexs[m]；

}}}}

//輸出功能

for(intn=0;n<number;n++)

(

if(n!=i)

{if(dist[n].dist<1000)

|

cout?vexs[i至lj"V<vexs|nkV”的最近距離為：n?distLn].dist?endl;

cou通過(guò)的頂點(diǎn)為:"<Vvexs[i]?M--->

for(intp=0;p<dist[n].nodenum;p++)

{cout?dist[n].way

}

cout<<vexs[n]?endl;

)

eIse

cout?vexs[i]vv“到“v<vexs沒(méi)有通路ndl；

}}}

voidMgraph：:Floyd()

(

inti,j,m,n;

for(i=0;i<number;i++)

for(j=0;j<number;j++)

for(m=O;m<number；m++)

P[i][j][m]=0;

for(i=0;i<number；i++)

for(j=0;j<number;j++)

(

Darcs[i][j];

if(D[i][j]<1000)

(

P[ilU][i]=l；

P|i][J]Ej]=1；