數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--用c#語言解決最短路徑的問題

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》單元設(shè)計(jì)報(bào)告</p><p><b>　　單元設(shè)計(jì)任務(wù)書</b></p><p>　　軟件學(xué)院 軟件開發(fā)與項(xiàng)目管理專業(yè) </p><p>　　用C#語言解決最短路徑的問題</p><p>　　學(xué)生姓名： 指導(dǎo)老

2、師：XXXX</p><p>　　摘 要 本單元設(shè)計(jì)主要解決設(shè)計(jì)一個程序，用戶輸入起始位置，就能得到該點(diǎn)到其他點(diǎn)的最短路線，及最短距離。 程序運(yùn)行平臺為Windows 98/2000/XP/7，.net 2.0框架。在程序設(shè)計(jì)中，采用了C#面向?qū)ο缶幊陶Z言，將功能實(shí)現(xiàn)封裝在業(yè)務(wù)類中，對問題中的要求做出了準(zhǔn)確的實(shí)現(xiàn)。程序通過調(diào)試運(yùn)行，實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)。 </p><p>　　關(guān)鍵詞 C#

3、；業(yè)務(wù)類、業(yè)務(wù)方法、控制臺界面 迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）</p><p><b>　　1 引 言</b></p><p>　　本單元設(shè)計(jì)主要解決設(shè)計(jì)一個程序，用戶輸入起始位置，就能得到該點(diǎn)到其他點(diǎn)的最短路線，及最短距離。（各點(diǎn)之間的距離要求事先錄入）</p><p>　　1.1 單元設(shè)計(jì)目的</p>

4、<p>　　通過這次單元設(shè)計(jì)進(jìn)一步了解了最短路徑的算法。</p><p>　　1.2 單元設(shè)計(jì)內(nèi)容</p><p>　　本次單元設(shè)計(jì)內(nèi)容主要是利用迪杰斯特拉求解最短路徑。</p><p>　　最短路徑問題是圖論研究中的一個經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。 算法具體的形式包括： </p><p&g

5、t;　　確定起點(diǎn)的最短路徑問題 - 即已知起始結(jié)點(diǎn)，求最短路徑的問題。 </p><p>　　確定終點(diǎn)的最短路徑問題 - 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。 </p><p>　　確定起點(diǎn)終點(diǎn)的最短路徑問題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 </p><p>　　全局最短路徑問題 - 求圖中所有的最短路徑。</p>

6、;<p><b>　　2 需求分析</b></p><p><b>　　3 概要設(shè)計(jì)</b></p><p>　　3.1 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)存儲表示</p><p>　　這方面使用二維數(shù)組n[MAX][MAX]來靜態(tài)存儲不超過MAX行MAX列的距離方陣。</p><p><b>

7、　　3.2 程序結(jié)構(gòu)</b></p><p>　　主要使用與實(shí)現(xiàn)如下類：</p><p>　　(1)界面類MagicSquareCon，用于調(diào)用業(yè)務(wù)類，實(shí)現(xiàn)最短路線，及距離的輸出。</p><p>　　(2業(yè)務(wù)類Dijkstra，用于實(shí)現(xiàn)需求分析的功能，主要包括以下方法或?qū)傩裕?lt;/p><p>　　int[] PathArc: 路

8、徑下標(biāo)的數(shù)組</p><p>　　int[] ShortPathTable 存儲到各點(diǎn)最短路徑的權(quán)值和</p><p>　　ShortPath(int init) 計(jì)算init 點(diǎn)到各頂點(diǎn)的最最短路徑</p><p>　　3.3 函數(shù)邏輯功能調(diào)用圖</p><p>　　圖3.1 邏輯功能調(diào)用圖</p><p>&l

9、t;b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　int[] PathArc路徑下標(biāo)的數(shù)組 比如PathArc為P:{0,0,1,4,2,4,3,6,7}，P[8]=7,它的意思是v0到v8的最短路徑，頂點(diǎn)v8的前驅(qū)頂點(diǎn)是v7, 再用</p><p>　　P[7]=6 表示v7的前驅(qū)是v6,P[6]=3,表示v6的前驅(qū)是v3,這樣就得到v0至</p>&

10、lt;p>　　V8的最短路徑為v8-v7-v6-v3-v4-v2-v1-v0,即v0->v1->v2->v4->v3->v6->v7-</p><p><b>　　->v8。 </b></p><p>　　（2）int[] ShortPathTable 存儲到各點(diǎn)最短路徑的權(quán)值和。比如數(shù)組為{0,1,4,7,5,8}&

11、lt;/p><p>　　表示v0到v1的距離是1，v0到v4的距離是5。</p><p>　?。?）ShortPath(int init) 計(jì)算init 點(diǎn)到各頂點(diǎn)最短路徑的方法，構(gòu)造函數(shù)調(diào)用。</p><p>　　3.4 程序執(zhí)行流程圖</p><p><b>　　5 運(yùn)行環(huán)境與結(jié)果</b></p><

12、p>　　5.1程序運(yùn)行環(huán)境:</p><p>　　VS2008 VS2005開發(fā)平臺。</p><p>　　5.2 程序運(yùn)行結(jié)果</p><p>　　（1）運(yùn)行程序，根據(jù)提示輸入指令,當(dāng)v0=0時，程序運(yùn)行結(jié)果如圖4.2.1所示</p><p><b>　　5 結(jié)束語</b></p><p>

13、;　　本次單元設(shè)計(jì)我選擇了一個最短路徑的算法實(shí)現(xiàn)。通過不懈的努力終于掌握這兩個經(jīng)典的算法 迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）</p><p>　　在編程實(shí)現(xiàn)的過程中，我進(jìn)一步掌握和熟悉了而為數(shù)組的應(yīng)用，并熟悉了將問題分解在組裝的解決方法和函數(shù)的調(diào)用。</p><p>　　通過這次課程設(shè)計(jì)，使我們學(xué)到了一些以前沒有學(xué)過的知識，使我們對程序設(shè)計(jì)有了更深層次的認(rèn)識和理解，懂得

14、了靈活運(yùn)用。</p><p>　　最后，由衷的向我的指導(dǎo)老師表示衷心的感謝，是她的指導(dǎo)和要求，才使我的課程設(shè)計(jì)有了較為完善的一面，才有了我能力的提高，并使我得到了充分的鍛煉，同時也感謝我的同學(xué)，是他們幫助我解決了一些問題。 </p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]黎明志. 數(shù)據(jù)結(jié)構(gòu)—用C語言描述. 北京：中國

15、水利水電出版社，2006，1</p><p><b>　　附錄 源程序代碼</b></p><p>　　// 程序名稱：SortPath</p><p>　　// 程序功能：最短路線</p><p>　　// 程序作者：HYH</p><p>　　// 最后修改日期：2011-12-2</

16、p><p><b>　　二維數(shù)組構(gòu)造圖：</b></p><p>　　using System;</p><p>　　using System.Collections.Generic;</p><p>　　using System.Linq;</p><p>　　using System.Text;&

17、lt;/p><p>　　namespace SortPath</p><p><b>　　{</b></p><p>　　public class MGraph</p><p><b>　　{</b></p><p>　　public int[] Vexs { private s

18、et; get; }</p><p>　　public int[,] Arc { private set; get; }</p><p>　　public int NumEdges { private set; get; } //圖的頂點(diǎn)數(shù)</p><p>　　public int Width { private set; get; }</p><

19、;p>　　/// <summary></p><p><b>　　/// 圖構(gòu)造器</b></p><p>　　/// </summary></p><p>　　/// <param name="width">頂點(diǎn)數(shù)</param></p><p>

20、;　　/// <param name="array">二維數(shù)組</param></p><p>　　/// <param name="arrayName">一維數(shù)組</param></p><p>　　public MGraph(int width, int[,] array,int[] arrayNa

21、me)</p><p><b>　　{</b></p><p>　　Vexs = arrayName;</p><p>　　Arc = array;</p><p>　　Width = width;</p><p>　　NumEdges = width;</p><p>&

22、lt;b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　關(guān)鍵算法：</b></p><p>　　using System;</p><p>　　using S

23、ystem.Collections.Generic;</p><p>　　using System.Linq;</p><p>　　using System.Text;</p><p>　　namespace SortPath</p><p><b>　　{</b></p><p>　　publi

24、c class Dijkstra</p><p><b>　　{</b></p><p>　　public int[] PathArc { private set; get; } //儲存路徑下標(biāo)的數(shù)組</p><p>　　public int[] ShortPathTable { private set; get; } //存儲到各點(diǎn)最短路

25、徑的權(quán)值和</p><p>　　MGraph mGraph;</p><p>　　int numVertexes;</p><p>　　public Dijkstra(int vo,MGraph mgraph)</p><p><b>　　{</b></p><p>　　mGraph = mgra

26、ph;</p><p>　　PathArc = new int[mgraph.Width]; // 路徑數(shù)組</p><p>　　ShortPathTable = new int[mgraph.Width]; //路徑權(quán)值數(shù)組</p><p>　　numVertexes = mgraph.Width;</p><p>　　ShortPath

27、(vo);</p><p><b>　　}</b></p><p>　　private void ShortPath(int init)</p><p><b>　　{</b></p><p>　　int v, w, k=0, min;</p><p>　　bool[] fi

28、nal = new bool[mGraph.Width]; //final[w]=true 表示求得頂點(diǎn)v0 至vw的最短路徑</p><p>　　for (v = 0; v < numVertexes; v++)</p><p><b>　　{</b></p><p>　　ShortPathTable[v] = mGraph.Arc[i

29、nit, v];//與v0有連線的頂點(diǎn)賦權(quán)值</p><p><b>　　}</b></p><p>　　ShortPathTable[0] = 0; //v0 至v0 的路徑為0</p><p>　　final[0] = true; //v0至v0 不需要求路徑</p><p>　　for (v = 1; v <

30、 numVertexes; v++)</p><p><b>　　{</b></p><p>　　min = int.MaxValue;</p><p>　　for (w = 0; w < numVertexes; w++)</p><p><b>　　{</b></p><

31、;p>　　if(!final[w]&&ShortPathTable[w]<min)</p><p><b>　　{</b></p><p><b>　　k=w;</b></p><p>　　min=ShortPathTable[w];</p><p><b>　

32、　}</b></p><p><b>　　}</b></p><p>　　final[k] = true; //講找到的最近頂點(diǎn)置為true</p><p>　　for (w = 0; w < numVertexes; w++)</p><p><b>　　{</b></p&

33、gt;<p>　　if (!final[w] && (Convert.ToInt64(mGraph.Arc[k, w])+min< ShortPathTable[w]))</p><p><b>　　{</b></p><p>　　ShortPathTable[w] = mGraph.Arc[k, w] + min ;</p&

34、gt;<p>　　PathArc[w] = k;</p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　} </p><p><b>　　} </b></p>&l

35、t;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　界面層：</b></p><p>　　using System;</p><p>　　using System.Collections.Generic;</p>

36、<p>　　using System.Linq;</p><p>　　using System.Text;</p><p>　　using SortPath;</p><p>　　namespace PathTest</p><p><b>　　{</b></p><p>　　cla

37、ss Program</p><p><b>　　{</b></p><p>　　static int vwrtexes = 9; //頂點(diǎn)</p><p>　　int[] Varray = new int[vwrtexes];</p><p>　　int[,] edgesArray = new int[vwrtexe

38、s, vwrtexes];</p><p>　　static MGraph Mg;</p><p>　　static void Main(string[] args)</p><p><b>　　{</b></p><p>　　int init = 0; //出發(fā)啟始位置</p><p>

39、　　Program p = new Program();</p><p>　　p.Init(); </p><p>　　Mg= new MGraph(vwrtexes, p.edgesArray, p.Varray);</p><p>　　Dijkstra di = new Dijkstra(init, Mg);</p><p>　　

40、int[] Path = di.ShortPathTable;</p><p>　　int[] Arc = di.PathArc;</p><p>　　Console.WriteLine("輸入起始位置：");</p><p>　　init = Convert.ToInt32(Console.ReadLine());</p><

41、;p>　　p.Show(Arc, Path, init);</p><p><b>　　}</b></p><p>　　將各點(diǎn)之間的距離 初始化到二維數(shù)組中</p><p>　　private void Init()</p><p><b>　　{</b></p><p&g

42、t;　　for (int i = 0; i < vwrtexes; i++)</p><p><b>　　{</b></p><p>　　Varray[i] = i;</p><p>　　for (int j = 0; j < vwrtexes; j++)</p><p><b>　　{</b

43、></p><p>　　edgesArray[i, j] = int.MaxValue;</p><p>　　if (i == j)</p><p>　　edgesArray[i, j] = 0;</p><p><b>　　}</b></p><p><b>　　}</b&

44、gt;</p><p>　　edgesArray[0, 1] = 1;</p><p>　　edgesArray[0, 2] = 5;</p><p>　　edgesArray[1, 2] = 3;</p><p>　　edgesArray[1, 3] = 7;</p><p>　　edgesArray[1, 4] =

45、 5;</p><p>　　edgesArray[2, 4] = 1;</p><p>　　edgesArray[2, 5] = 7;</p><p>　　edgesArray[3, 4] = 2;</p><p>　　edgesArray[3, 6] = 3;</p><p>　　edgesArray[4, 5] =

46、 3;</p><p>　　edgesArray[4, 6] = 6;</p><p>　　edgesArray[4, 7] = 9;</p><p>　　edgesArray[5, 7] = 5;</p><p>　　edgesArray[6, 7] = 2;</p><p>　　edgesArray[6, 8] =

47、 7;</p><p>　　edgesArray[7, 8] = 4;</p><p>　　for (int i = 0; i < vwrtexes; i++)</p><p>　　for (int j = i; j < vwrtexes; j++)</p><p>　　edgesArray[j, i] = edgesArray[

48、i, j];</p><p><b>　　}</b></p><p>　　顯示最短路線信息 及最短距離</p><p>　　private void Show(int [] arc,int[] path,int v)</p><p><b>　　{</b></p><p>　

49、　Console.WriteLine("最短路徑倒序如下：");</p><p>　　for (int i = 1; i < vwrtexes; i++)</p><p><b>　　{</b></p><p>　　Console.Write("v{0}---v{1}", v, i);</p&

50、gt;<p>　　int j = i;</p><p>　　while (arc[j] != 0)</p><p><b>　　{</b></p><p>　　Console.Write(" " + arc[j]);</p><p>　　j = arc[j];</p>&l

51、t;p><b>　　}</b></p><p>　　Console.WriteLine();</p><p><b>　　}</b></p><p>　　Console.WriteLine("\n\n源點(diǎn)到各頂點(diǎn)的距離:");</p><p>　　for (int i =

52、1; i < vwrtexes; i++)</p><p>　　Console.WriteLine("v{0}----v{1}:{2}",v,Mg.Vexs[i],path[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p&