軟件基礎課程設計--從某個源點到其余各頂點的最短路徑

《軟件基礎課程設計--從某個源點到其余各頂點的最短路徑》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、北京信息科技大學軟件設計基礎課程設計題目：從某個源點到其余各頂點的最短路徑學院：信息與通信工程學院專業(yè)：通信工程專業(yè)學生姓名：班級/學號：指導老師：曹林徐湛楊瑋李振松起止時間：2013-9-22至2013-11-6任務書76任務書題目7從某個源點到其余各頂點的最短路徑（難度系數9）主要內容1、假設西安、北京、沈陽、武漢4個城市構成小型交通網，4個城市表示圖的4個頂點，他們構成了無向連通圖。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。2、學會建立圖的鄰接表，理解圖的基本概念。3、學會編寫DLL函數。4、根據自己構建的連通圖，利用Dijkstra算法求

2、從某個源點到其余各頂點的最短路徑。5、掌握C++編程環(huán)境的基本調試方法，熟練使用可視化C++編程工具。設計要求1、上交課程設計的書面材料，要求打印。包括課程設計任務書、主要內容，源程序，對程序的功能進行客觀評價，明確指出自己編寫了哪些具體函數。2、上交電子版源程序，包括鄰接表建立程序、Dijkstra算法。3、自己編寫一個求素數函數，把它書寫成一個動態(tài)鏈接庫形式，并在主函數中調用它。嘗試把自己編寫的程序寫成動態(tài)鏈接庫和靜態(tài)鏈接庫形式（無需上交），并比較以下三種EXE文件的大小。A：調用靜態(tài)鏈接庫生成的EXE執(zhí)行文件。B：調用動態(tài)鏈接庫生成的EXE執(zhí)行文件。C：直接調用函數生成的EXE執(zhí)行文

3、件。主要儀器設備計算機一臺，安裝WindowsXP操作系統(tǒng)、MicrosoftVisualC++6.0、MSDNLibrary。主要參考文獻[1]侯俊杰.深入淺出MFC(第二版)[M].武漢：華中科技大學出版社,2001.[2]譚浩強.C程序設計（第二版）[M].北京：清華大學出版社,1999..[3]孟彩霞.計算機軟件基礎[M].陜西：西安電子科技大學出版社,2003.[4]嚴蔚敏,吳偉民.數據結構[M].北京：清華大學出版社,2005.課程設計進度計劃（起止時間、工作內容）選做最短路徑題目的同學，2人1組，1人做Dijkstra算法，1人做Floyd算法，整個課程設計共20學時，具體進

4、度如下：4學時了解課題背景，選題，學習DLL，學習圖的基本概念。4學時編寫鄰接表建立程序。4學時Dijkstra算法。4學時嘗試利用Dijkstra算法求任意兩個頂點之間的最小距離。4學時調試程序，答辯。課程設計開始日期2013-9-22課程設計完成日期2013-11-6課程設計實驗室名稱計算中心機房地點健翔橋校區(qū)76摘要摘要本次課程設計的問題：假設西安、北京、沈陽、武漢4個城市構成小型交通網，4個城市表示圖的4個頂點，它們構成了無向連通圖。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；北京到武漢的最短路徑。本次課程設計中應用Dijkstra算法求最短路徑。通過一個圖的權值

5、矩陣求出它的每兩點間的最短路徑矩陣，從圖的帶權鄰接矩陣arcs(n×n)開始，遞歸地進行n次更新，按一個公式，構造出矩陣S(1)，又用同樣的公式由S(1)構造出S(2)…最后又用同樣的公式由S(n-1)構造出矩陣S(n)。矩陣S(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱S(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣p[j][k]來記錄兩點間的最短路徑。本次試驗進行的是無向的計算，不同城市之間的距離由開始進行輸入，最后顯示兩個城市之間的最短路徑。77目錄目錄任務書1摘要2目錄3正文4一、應用迪科斯徹（Dijkstra）算法計算最短路徑4二、Dijkstra求最短路徑的

6、基本思想4三、Dijkstra求最短路徑的步驟4四、程序說明5五、功能實現5六、程序設計（二）12七、課程設計總結16參考文獻17源代碼1897正文—從某個源點到其余各頂點的最短路徑一、應用迪科斯徹（Dijkstra）算法計算最短路徑假設西安、北京、沈陽、武漢4個城市構成小型交通網，4個城市表示圖的4個頂點，他們構成了無向連通圖。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。這里路徑指兩頂點間的通路，路徑的長度指所有經過的邊的總長。“最短路徑”的問題指當兩個頂點間通路多于一條時，如何找出邊長總和為最短的那條。Dijkstra提出按路徑長度遞增的次序求

7、最短路徑的方法。二、Dijkstra求最短路徑的基本思想把頂點分成兩組，第一組是已確定最短路徑的結點的集合，第二組是尚未確定最短路徑的結點的集合。按路徑長度遞增的次序逐個把第二組的頂點放到第一組中。設求從v0到其它各頂點間的最短路徑,則在任意時刻，從v0到第一組各頂點間的最短路徑都不大于從v0到第二組各頂點間的最短路徑。三、Dijkstra求最短路徑的步驟設圖以鄰接矩陣arcs存儲，矩陣中各元素的值為各邊的權值。頂點到自