軟件基礎(chǔ)課程設(shè)計--從某個源點到其余各頂點的最短路徑(已修改)
2025-06-20 17:24 本頁面
【正文】 北京信息科技大學 軟件 設(shè)計 基礎(chǔ)課程設(shè)計 題 目： 從某個源點到其余各頂點的最短路徑 學 院： 信息與通信工程學院 專 業(yè)： 通信工程專業(yè) 學生姓名： 班級 /學號 ： 指導老師： 曹林 徐湛 楊瑋 李振松 起止 時間： 2021922 至 2021116 任務(wù)書 1 題目 7 從某個源點到其余各頂點的最短路徑（難度系數(shù) 9） 主要 內(nèi)容 假設(shè)西安、北京、沈陽、武漢 4 個城市構(gòu)成小型交通網(wǎng)， 4 個城市表示圖的 4 個頂點，他們構(gòu)成了無向連通圖。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。 學會建立圖的鄰接表，理解圖的基本概念。 學會編寫 DLL 函數(shù)。 根據(jù)自己構(gòu)建的連通圖，利用 Dijkstra算法求 從某個源點到其余各頂點的最短路徑。 掌握 C++編程環(huán)境的基本調(diào)試方法，熟練使用可視化 C++編程工具。 設(shè)計 要求 上交課程設(shè)計的書面材料，要求打印。包括課程設(shè)計 任務(wù)書、 主要內(nèi)容， 源程序 ，對程序的功能進行客觀評價，明確指出自己編寫了哪些具體函數(shù) 。 上交電子版源程序 ，包括鄰 接表建立程序、 Dijkstra 算法 。 自己編寫一個求素數(shù)函數(shù)，把它書寫成一個動態(tài)鏈接庫形式，并在主函數(shù)中調(diào)用它。嘗試把自己編寫的程序?qū)懗蓜討B(tài)鏈接庫和靜態(tài)鏈接庫形式（無需上交），并比較以下三種 EXE 文件的大小。 A：調(diào)用靜態(tài)鏈接庫生成的 EXE 執(zhí)行文件。 B：調(diào)用動態(tài)鏈接庫生成的 EXE 執(zhí)行文件。 C：直接調(diào)用函數(shù)生成的 EXE 執(zhí)行文件。 主要 儀器 設(shè)備 計算機 一臺，安裝 Windows XP 操作系統(tǒng) 、 Microsoft Visual C++ 、 MSDN Library。 主要 參考 文獻 [1] 侯俊杰 . 深入淺出 MFC(第二版 )[M]. 武漢：華中科技大學出版社 , 2021. [2] 譚浩強 . C 程序設(shè)計（第二版） [M]. 北京 ：清華大學 出版社 , 1999.. [3] 孟彩霞 . 計算機軟件基礎(chǔ) [M]. 陜西：西安電子科技大學出版社 , 2021. [4] 嚴蔚敏 , 吳偉民 . 數(shù)據(jù)結(jié)構(gòu) [M]. 北京：清華大學出版社 , 2021. 課程設(shè)計進度計劃（起止時間、工作內(nèi)容） 選做最短路徑題目的同學， 2 人 1 組， 1 人做 Dijkstra 算法 ， 1 人做 Floyd 算法，整個課程設(shè)計共 20 學時，具體進度如下： 4 學時 了解 課題 背景，選題，學習 DLL，學習圖的基本概念。 4 學時 編寫鄰接表建立程序。 4 學時 Dijkstra 算法 。 4 學時 嘗試利用 Dijkstra 算法求任意兩個頂點之間的最小距離 。 4 學時 調(diào)試程序，答辯。 課程設(shè)計開始日期 2021922 課程設(shè)計完成日期 2021116 課程設(shè)計實驗室名稱 計算中心機房 地 點 健翔橋校區(qū) 摘要 2 摘要 本次課程設(shè)計的問題：假設(shè)西安、北京、沈陽、武漢 4 個城市構(gòu)成小型交通網(wǎng)， 4 個城市表示圖的 4 個頂點，它們構(gòu)成了無向 連通圖。以北京為源點，求北京到西安的最短路徑；求北京到沈陽的最短路徑；北京到武漢的最短路徑。 本次課程設(shè)計中應(yīng)用 Dijkstra 算法求最短路徑。通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣，從圖的帶權(quán)鄰接矩陣 arcs(n n)開始，遞歸地進行 n 次更新，按一個公式，構(gòu)造出矩陣 S(1)，又用同樣的 公式由 S(1)構(gòu)造出 S(2)?最后又用同樣的公式由 S(n1)構(gòu)造出矩陣 S(n)。矩陣 S(n)的 i行 j列元素便是 i號頂點到 j 號頂點的最短路徑長度，稱 S(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣 p[j][k]來記錄兩點間的最短路徑。 本次試驗 進行 的是 無向的計算，不同城市之間的距離由開始進行輸入，最后顯示兩個城市之間的最短路徑。 目錄 3 目錄 任務(wù)書 1 摘要
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1