單元點(diǎn)最短路徑算法的實(shí)現(xiàn) 課程設(shè)計(jì).doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)說(shuō)明書 單元點(diǎn)最短路徑算法的實(shí)現(xiàn)單元點(diǎn)最短路徑算法的實(shí)現(xiàn) 學(xué)生姓名 學(xué) 號(hào) 班 級(jí) 成 績(jī) 指導(dǎo)教師 余冬梅 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 2014 年 3 月 7 日 課程設(shè)計(jì)任務(wù)書 2013 2014 學(xué)年第學(xué)年第 2 學(xué)期學(xué)期 專業(yè) 學(xué)號(hào) 姓名 課程設(shè)計(jì)名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 單源點(diǎn)最短路徑算法的實(shí)現(xiàn) 完成期限 自 2014 年 2 月 24 日至 2014 年 3 月 7 日共 2 周 設(shè)計(jì)依據(jù) 要求及主要內(nèi)容 可另加附頁(yè) 最短路徑問(wèn)題是數(shù)據(jù)結(jié)構(gòu)中數(shù)組部分的重點(diǎn)和難點(diǎn)知識(shí) 它屬于圖結(jié)構(gòu)問(wèn)題 其解決方法也有不 少 如 Dijkstra A star 可自行選擇算法 本課程設(shè)計(jì)按以下的要求運(yùn)用 C C 結(jié)構(gòu)體 指針 數(shù)據(jù)結(jié)構(gòu)等基知識(shí)編程實(shí)現(xiàn) 任務(wù)要求 任務(wù)要求 1 闡述設(shè)計(jì)思想 畫出流程圖 2 任意建立存儲(chǔ) m 個(gè)頂點(diǎn) n 條邊的圖 3 按照用戶要求的 源點(diǎn)和目標(biāo)點(diǎn) 求出它們間的最短路徑 并打印出路徑 若無(wú)路徑需給出說(shuō)明 4 說(shuō)明測(cè)試方法 寫 出完整的運(yùn)行結(jié)果 較好的界面設(shè)計(jì) 5 按照格式要求完成課程設(shè)計(jì)說(shuō)明書 設(shè)計(jì)要求設(shè)計(jì)要求 1 問(wèn)題分析和任務(wù)定義 根據(jù)設(shè)計(jì)題目的要求 充分地分析和理解問(wèn)題 明確問(wèn)題要求做什么 而不是怎么做 限制條件是什么 確定問(wèn)題的輸入數(shù)據(jù)集合 2 邏輯設(shè)計(jì) 對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型 并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原 則劃分模塊 定義主程序模塊和各抽象數(shù)據(jù)類型 邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義 包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明 各個(gè)主要模塊的算法 并畫出模塊之間的調(diào)用關(guān) 系圖 3 詳細(xì)設(shè)計(jì) 定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法 在這個(gè)過(guò)程中 要綜合考慮系統(tǒng)功 能 使得系統(tǒng)結(jié)構(gòu)清晰 合理 簡(jiǎn)單和易于調(diào)試 抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝 基本操 作的規(guī)格說(shuō)明盡可能明確具體 詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精 寫出數(shù) 據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義 寫出函數(shù)形式的算法框架 4 程序編碼 把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序 同時(shí)加入一些注解和斷言 使 程序中邏輯概念清楚 5 程序調(diào)試與測(cè)試 能夠熟練掌握調(diào)試工具的各種功能 設(shè)計(jì)測(cè)試數(shù)據(jù)確保程序正確 調(diào)試正確 后 認(rèn)真整理源程序及其注釋 形成格式和風(fēng)格良好的源程序清單和結(jié)果 6 結(jié)果分析 程序運(yùn)行結(jié)果包括合法的輸入及其輸出結(jié)果和含有非法的輸入及其輸出結(jié)果 算法 的時(shí)間 空間復(fù)雜性分析 7 編寫課程設(shè)計(jì)報(bào)告 以上要求中前三個(gè)階段的任務(wù)完成后 先將設(shè)計(jì)說(shuō)明書的草稿交指導(dǎo)老師面審 審查合格后方可 進(jìn)入后續(xù)階段的工作 設(shè)計(jì)工作結(jié)束后 經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說(shuō)明書打印裝訂 指導(dǎo)教師 簽字 教研室主任 簽字 批準(zhǔn)日期 2014 年 2 月 23 日 課程設(shè)計(jì)評(píng)閱 評(píng)語(yǔ) 指導(dǎo)教師簽名 年 月 日 指導(dǎo)教師 余冬梅 教研室負(fù)責(zé)人 申靜 摘摘 要要 本系統(tǒng)以 VC 作為軟件開(kāi)發(fā)環(huán)境 C 語(yǔ)言作為程序開(kāi)發(fā)語(yǔ)言 鄰接矩陣作為存儲(chǔ)結(jié)構(gòu) 設(shè)計(jì)與 實(shí)現(xiàn)了最短路徑運(yùn)算 該系統(tǒng)實(shí)現(xiàn)了有向圖的存儲(chǔ) 最短路徑的運(yùn)算等主要功能 依照該系統(tǒng)可以解 決生活中許多問(wèn)題 比如交通路線的選擇 工程時(shí)間的預(yù)算等等 讓人們可以做出合理的選擇 本系 統(tǒng)通過(guò)分析課題的背景 意義 要求 分別從課題描述 邏輯設(shè)計(jì) 算法設(shè)計(jì) 調(diào)試與測(cè)試等各個(gè)方 面詳細(xì)介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程 最后對(duì)系統(tǒng)的完成情況進(jìn)行了總結(jié) 界面清晰 操作簡(jiǎn)單 易 于用戶接受 關(guān)鍵詞關(guān)鍵詞 VC 鄰接矩陣 最短路徑 目錄目錄 1 課題描述 1 2 問(wèn)題分析與任務(wù)定義 2 2 1 問(wèn)題分析 2 2 2 任務(wù)定義 2 3 算法設(shè)計(jì) 3 3 1 圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu) 3 3 2 DIJKSTRA算法思想 4 4 系統(tǒng)邏輯設(shè)計(jì) 5 4 1 主函數(shù)流程圖如圖 4 1 所示 5 4 2 CREATE函數(shù)流程圖如圖 4 2 所示 6 4 3 DIJKSTRA函數(shù)流程圖如圖 4 3 所示 8 4 源代碼 11 5 調(diào)試與測(cè)試 14 6 總結(jié) 16 參考文獻(xiàn) 17 0 1 1 課題描述課題描述 乘車旅行的人大多數(shù)都希望找出到目的地盡可能短 花費(fèi)少的行程 那么如何找出從 出發(fā)點(diǎn)到目的地的最短路徑 由于路徑比較多 所以用手工計(jì)算起來(lái)比較復(fù)雜 抽象 因 此人們用計(jì)算機(jī)語(yǔ)言代替手工計(jì)算來(lái)求得最短路徑 而在計(jì)算機(jī)語(yǔ)言中迪杰斯拉算法比較 常用 簡(jiǎn)捷 故人們經(jīng)常借助計(jì)算機(jī)程序用迪杰斯拉算法求得單源點(diǎn)的最短路徑 這樣可 以廣泛的提高效率 而且條理清晰 通俗易懂 1 2 2 問(wèn)題分析與任務(wù)定義問(wèn)題分析與任務(wù)定義 2 1 問(wèn)題分析 本系統(tǒng)是要解決的是單源點(diǎn)最短路徑問(wèn)題 設(shè)計(jì)程序 實(shí)現(xiàn)最短路徑的求法 系 統(tǒng)需要達(dá)到的主要功能如下 1 編寫算法能夠建立帶權(quán)圖 并能夠用 Dijkstra 算法求該圖的最短路徑 2 能夠選擇圖上的任意一頂點(diǎn)做為開(kāi)始節(jié)點(diǎn) 最短路徑輸出不必采用圖形方式 可頂點(diǎn)序列方式輸出 3 根據(jù)課設(shè)題目要求 擬將整體程序分為三大模塊 兩個(gè)子模塊相互獨(dú)立 沒(méi) 有嵌套調(diào)用的情況 在主模塊中調(diào)用上面兩個(gè)子模塊 2 2 任務(wù)定義 根據(jù)課設(shè)題目要求 擬將整體程序分為三大模塊 兩個(gè)子模塊相互獨(dú)立 沒(méi)有嵌 套調(diào)用的情況 在主模塊中調(diào)用上面兩個(gè)子模塊以下是三個(gè)模塊的大體分析 1 建立有向圖的存儲(chǔ)結(jié)構(gòu) 2 應(yīng)用 Dijkstra 算法求出該有向圖的最短路徑 3 在主函數(shù)中調(diào)用兩個(gè)子函數(shù) 完成最短路徑的程序設(shè) 2 3 3 算法設(shè)計(jì)算法設(shè)計(jì) 3 1 圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu) 一個(gè)圖的鄰接矩陣表示唯一的 故在圖的鄰接矩陣表示中 除了需要用一個(gè)二維 數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣外 通常還需要使用一個(gè)具有 n 個(gè)元素的一維 數(shù)組存儲(chǔ)頂點(diǎn)信息 其中下標(biāo)為 i 的元素存儲(chǔ)頂點(diǎn) vi 的信息 本設(shè)計(jì)是基于類 C 語(yǔ)言 的算法描述 因此 圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下 define MVNum 50 typedef struct VertexType vexs MVNum Adjmatrix arcs MVNum MVNum Mgraph 在本系統(tǒng)中 以鄰接矩陣存儲(chǔ)有向圖 如圖 3 1a 中有向圖 G 所示 其鄰接矩陣 為圖 3 1b 所示 20 1010 505 f ea b c d 100 60 30 圖 3 1a 有向圖 G 10 30 100 5 50 10 20 60 b a e f 5 50 圖 3 1a 有向圖 G 圖 3 1b G 的鄰接矩陣 10 30 100 5 50 10 20 60 圖 3 1b G 的鄰接矩陣 圖 3 1b G 的鄰接矩陣 3 3 2 Dijkstra 算法思想 1 Dijkstra 算法核心是貪心 實(shí)質(zhì)是按路徑長(zhǎng)度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算 法 用自然語(yǔ)言描述如下 初始化 S 和 D 置空最短路 徑終點(diǎn)集 置初始的最短路徑值 S v1 TRUE D v1 0 While S 集中的頂點(diǎn)數(shù) n 開(kāi)始循環(huán) 每次求的 v1 到某個(gè) v 頂點(diǎn)的最短路徑 并將 v 加到 S 集中 S v TRUE 更新當(dāng)前最短路徑及距離 2 Dijkstra 算法結(jié)束后 通過(guò)設(shè)置一個(gè)數(shù)組記錄下一個(gè)節(jié)點(diǎn)的前趨節(jié)點(diǎn) 然后 通過(guò)倒敘的方式輸出該最短路徑 4 4 4 系統(tǒng)邏輯設(shè)計(jì)系統(tǒng)邏輯設(shè)計(jì) 4 1 主函數(shù)流程圖如圖 4 1 所示 3 1 主函數(shù)流程圖 4 2 Create 函數(shù)流程圖 開(kāi)始 輸入數(shù)據(jù) 調(diào)用 Create 函數(shù) 調(diào)用 Dijkstra 函數(shù) k 1 開(kāi)始 輸入頂點(diǎn)個(gè)數(shù)和邊數(shù) m n 調(diào)用 Create 函數(shù) 建立圖的鄰接矩陣 請(qǐng)輸入初始點(diǎn) v 調(diào)用 Dijkstra 函數(shù) 求得最短路徑 結(jié)束 圖 4 1 主函數(shù)流程圖 Y N 5 4 2 Create 函數(shù)流程圖如圖 4 2 所示 開(kāi)始 定義頂點(diǎn)序號(hào) i 1 頂點(diǎn)數(shù) m 邊 數(shù) n i m Y 存入一維向量 G vexs i i i i 1 N i 1 i m Y j 1 jarcs i j w 變量 k 1 k n 給鄰接矩陣有關(guān)單元賦權(quán)值 w G arcs i j w k k 1 結(jié)束 圖 4 2 Create 函數(shù)流程圖 Y N 定位 i j i a a 1 j b a 1 接上一頁(yè) 7 4 3 Dijkstra 函數(shù)流程圖如圖 4 3 所示 開(kāi)始 定義 G 中 v1 到其余頂點(diǎn) v 的最短路徑 帶權(quán)長(zhǎng)度 及最短路徑終點(diǎn)的集合 int D MVNum P MVNum boolean S MVNum 定義頂點(diǎn)數(shù) int m v 1 v m Y 置空 S S v FALSE D v G arcs v1 v 若權(quán)值小于最大值 無(wú)窮 D v Maxint Y P v v1 v v 1 P v 0 N 初始化 v1 頂點(diǎn)屬于 s 集 D v1 0 S v1 TRUE 開(kāi)始主循環(huán) 每次求得 v1 到某個(gè) v 頂點(diǎn)的最短路徑 并加 v 到 s 集 i 2 N 接下一頁(yè) 8 S v TRUE i m mm m 當(dāng)前所知離 v1 頂點(diǎn)的最近距離 min Maxint 頂點(diǎn)變量 w 1 w m Y v w W 頂點(diǎn)離 v1 更近 min D w S v TRUE w w 1 Y w 1 w m 修改 D w P w D w D v G arcs v w P w v w w 1 i i 1 Y N N Y N 接上一頁(yè) S w 定義頂點(diǎn) typedef int Adjmatrix typedef enum FALSE TRUE boolean typedef struct 圖的鄰接矩陣 VertexType vexs MVNum 頂點(diǎn)向量 存放頂點(diǎn)的一維數(shù)組 Adjmatrix arcs MVNum MVNum 鄰接矩陣二維數(shù)組 MGraph 定義鄰接矩陣結(jié)構(gòu)類型 void CreateMGraph MGraph G int m int n 采用數(shù)組 鄰接矩陣 表示法 構(gòu)造圖 G int i j k w char a b for i 1 ivexs i i for i 1 i m i 初始化鄰接矩陣 for j 1 jarcs i j Maxint printf 輸入 d 條邊的 i j 及 w n n for k 1 karcs i j w 弧的權(quán)值 printf 有向圖的存儲(chǔ)結(jié)構(gòu)建立完成 n printf n void Dijkstra MGraph G int v1 int m 用 Dijkstra 算法求 G 中 v1 頂點(diǎn)到其余頂點(diǎn) v 的最短路徑 p v 及帶權(quán)長(zhǎng)度 D v 11 int D MVNum P MVNum int v i w min boolean S MVNum S 以求得最短路徑的終點(diǎn)的集合 for v 1 v m v S v FALSE D v G arcs v1 v if D v Maxint P v v1 else P v 0 D v1 0 S v1 TRUE 初始化 v1 頂點(diǎn)屬于 s 集 開(kāi)始主循環(huán) 每次求得 v1 到某個(gè) v 頂點(diǎn)的最短路徑 并加 v 到 s 集 for i 2 i m i 其余 n 1 個(gè)頂點(diǎn) min Maxint 當(dāng)前所知離 v1 頂點(diǎn)的最近距離 for w 1 w m w if S w min D w w 頂點(diǎn)離 v1 頂點(diǎn)更近 S v TRUE for w 1 w m w 更新當(dāng)前最短路徑及距離 if S w P w v printf 路徑長(zhǎng)度 路徑 n for i 1 i m i printf 5d D i printf 12c i 1 a v P i while v 0 12 printf c v 1 a v P v printf n void main MGraph G int m n v char ch printf 輸入所需圖的頂點(diǎn)個(gè)數(shù)和邊數(shù) m n scanf d d CreateMGraph while v m printf 求最短路徑 請(qǐng)輸入初始點(diǎn) v fflush stdin scanf c printf n v ch a 1 Dijkstra G v m 13 5 5 調(diào)試與測(cè)試調(diào)試與測(cè)試 1 合法數(shù)據(jù)測(cè)試結(jié)果如圖 5 1 所示 圖 5 1 合法數(shù)據(jù)測(cè)試結(jié)果 14 2 非法數(shù)據(jù)測(cè)試結(jié)果如圖 5 2 所示 圖 5 2 非法數(shù)據(jù)測(cè)試結(jié)果 當(dāng)前任務(wù)已達(dá)到任務(wù)目標(biāo) 對(duì)于 n 個(gè)頂點(diǎn)的有向圖 求一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路 徑的時(shí)間為 O n 調(diào)整最短路徑的循環(huán)共執(zhí)行 n 1 次 所以 時(shí)間復(fù)雜度是 O n2 采用 鄰接矩陣存儲(chǔ)有向圖 應(yīng)處理每?jī)蓚€(gè)頂點(diǎn)之間的關(guān)系 所以空間復(fù)雜度為 O n2 15 6 6 總結(jié)總結(jié) 本次課程設(shè)計(jì)涉及到的范圍很廣 讓我比較系統(tǒng)的對(duì) C 語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)進(jìn)行了一 次整理和復(fù)習(xí) 本系統(tǒng)存在的問(wèn)題主要是程序完成后 調(diào)試時(shí)沒(méi)有發(fā)現(xiàn)問(wèn)題 但是當(dāng)輸入 開(kāi)始節(jié)點(diǎn)后 運(yùn)行框卻不停的出現(xiàn) a 后來(lái)重新檢查程序時(shí)發(fā)現(xiàn) for 循環(huán)的括號(hào)后面 多了一個(gè) 去掉該分號(hào)之后 程序可以運(yùn)行 在這次課程設(shè)計(jì)中我體會(huì)到 C 語(yǔ)言超強(qiáng) 的邏輯性以及能夠熟練使用 VC 編譯環(huán)境的重要性 對(duì) C 語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)這兩門課程有了 新的認(rèn)識(shí) 它們既有聯(lián)系 又相互區(qū)別 在編寫程序過(guò)程中要靈活應(yīng)用 我對(duì)數(shù)據(jù)結(jié)構(gòu)的 理解還有待加強(qiáng) 這次課程設(shè)計(jì)應(yīng)用的算法是 Dijkstra 算法 在學(xué)習(xí)的過(guò)程中自己對(duì)這方 面的知識(shí)比較生疏 所以在算法設(shè)計(jì)過(guò)程中比較困難 尤其是設(shè)計(jì) Dijkstra 算法的流程圖