簡介全國交通出行咨詢模擬系統(tǒng)C語言實(shí)現(xiàn)源碼包是一份數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)項(xiàng)目面向高校計(jì)算機(jī)相關(guān)專業(yè)學(xué)生在課程設(shè)計(jì)、期末大作業(yè)中的直接參考與復(fù)用可作為完整方案下載即用。項(xiàng)目以全國城市間交通網(wǎng)絡(luò)為背景綜合運(yùn)用圖存儲(chǔ)、最短路徑查詢、鄰接表等核心數(shù)據(jù)結(jié)構(gòu)知識(shí)涵蓋公路、鐵路、航班等多類交通方式并已獲導(dǎo)師指導(dǎo)、以97分高分通過驗(yàn)收。壓縮包共10個(gè)文件核心為5個(gè)頭文件與1個(gè)C主程序分別承擔(dān)系統(tǒng)模塊接口與主邏輯另含3個(gè)文本數(shù)據(jù)文件用于城市、航班、火車信息初始化數(shù)據(jù)格式簡潔、便于按需修改同時(shí)附有1份README說明文檔整體約16KB目錄結(jié)構(gòu)清晰便于快速閱讀和二次開發(fā)。目前已有308人學(xué)習(xí)下載。下載解壓后即可編譯運(yùn)行無需修改能幫助使用者快速完成一份結(jié)構(gòu)完整、可演示的課程設(shè)計(jì)也可作為理解交通咨詢模擬算法實(shí)現(xiàn)的參考資料代碼注釋與模塊劃分便于進(jìn)一步擴(kuò)展功能并適合在課程答辯中直接演示。1. 全國交通出行咨詢模擬系統(tǒng)一張帶權(quán)圖把“出行咨詢”變成一道最短路徑題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)里“全國交通出行咨詢模擬系統(tǒng)”這類題目幾乎年年換皮出現(xiàn)。它聽上去要做成一個(gè)小型產(chǎn)品剝開來看骨架其實(shí)非常固定把城市抽象成頂點(diǎn)把交通線路抽象成帶權(quán)邊然后用最短路徑算法回答“從A市到B市怎么走最近、換乘最少”。真正讓初學(xué)者卡住的不是“全國”有多大而是C語言里怎么組織這張圖、怎么把文本數(shù)據(jù)可靠地加載進(jìn)內(nèi)存、怎么讓算法結(jié)果以看得懂的方式輸出。這篇文章按我實(shí)際做課設(shè)時(shí)慣用的路線從建模、存儲(chǔ)、算法選型、交互菜單到排錯(cuò)整體走一遍最后給出測(cè)試數(shù)據(jù)和答辯擴(kuò)展方向。2. 建模與存儲(chǔ)把交通網(wǎng)變成C語言能讀懂的圖2.1 為什么是一張無向帶權(quán)圖城市、線路和權(quán)重怎么映射交通出行咨詢這件事核心信息只有兩類有哪些城市哪些城市之間有線路、線路代價(jià)是多少。城市就是圖的頂點(diǎn)線路就是連接兩個(gè)頂點(diǎn)的邊邊的權(quán)重可以表示距離、時(shí)間或票價(jià)。換乘信息不需要額外存它可以從路徑經(jīng)過的邊數(shù)推導(dǎo)出來。最常見的做法是把全國交通網(wǎng)建模成一張無向帶權(quán)圖?；疖?、長途汽車大多是雙向運(yùn)行所以邊按無向處理存的時(shí)候?qū)ΨQ寫入鄰接矩陣。權(quán)重用什么口徑?jīng)Q定了系統(tǒng)的查詢標(biāo)題。如果課程設(shè)計(jì)題目寫的是“最短路徑”權(quán)重用公里數(shù)如果寫的是“最少時(shí)間”權(quán)重就存分鐘數(shù)兩者都做就需要準(zhǔn)備兩套邊權(quán)或者運(yùn)行時(shí)動(dòng)態(tài)替換。這一步先做結(jié)構(gòu)體定義。我用一個(gè)全局圖對(duì)象來裝城市表和鄰接矩陣后續(xù)所有函數(shù)都操作它省去在函數(shù)間反復(fù)傳指針的麻煩。課程設(shè)計(jì)規(guī)模下幾十個(gè)城市鄰接矩陣?yán)速M(fèi)的空間完全可以接受。#include stdio.h #include stdlib.h #include string.h #define MAX_CITY 256 #define INF 1000000000 // 1e9表示不可達(dá) typedef struct { int id; // 城市編號(hào)直接當(dāng)數(shù)組下標(biāo)用 char name[64]; // 城市名 } City; typedef struct { int n; // 當(dāng)前城市數(shù)量 City cities[MAX_CITY]; // 城市表 int edge[MAX_CITY][MAX_CITY]; // 鄰接矩陣 } TransportGraph; TransportGraph g_graph;City 結(jié)構(gòu)體把編號(hào)和名字綁在一起方便按數(shù)組下標(biāo)訪問城市名。TransportGraph 里 n 表示有效頂點(diǎn)數(shù)量edge 是鄰接矩陣edge[i][j] 存放 i 到 j 的代價(jià)。這里的編號(hào)策略我建議直接讓文件的 id 等于數(shù)組下標(biāo)從 0 開始后面所有算法都不用再做轉(zhuǎn)換少一類 bug。2.2 鄰接矩陣還是鄰接表課程設(shè)計(jì)規(guī)模下怎么選很多教材把鄰接表和鄰接矩陣放在一起講學(xué)生就容易糾結(jié)。其實(shí)選擇標(biāo)準(zhǔn)很簡單頂點(diǎn)少、邊比較密、要反復(fù)查詢?nèi)我鈨牲c(diǎn)關(guān)系用鄰接矩陣頂點(diǎn)多、邊稀疏、經(jīng)常只沿著某幾個(gè)鄰居遍歷用鄰接表。交通咨詢系統(tǒng)里查詢頻繁最短路徑算法每次都要掃描當(dāng)前頂點(diǎn)的所有鄰居鄰接矩陣的隨機(jī)訪問是一步到位代碼也直觀。全國幾百個(gè)城市矩陣大小 500×500每個(gè) int 占 4 字節(jié)總共約 1MB完全不是負(fù)擔(dān)。如果堅(jiān)持鄰接表路徑回溯、判斷兩點(diǎn)是否直連、Floyd 預(yù)計(jì)算都會(huì)變得麻煩課設(shè)答辯時(shí)還要多解釋一套鏈?zhǔn)浇Y(jié)構(gòu)。所以這個(gè)項(xiàng)目我一般直接上鄰接矩陣。只有當(dāng)題目明確要求“城市數(shù)量超過 1000內(nèi)存受限”時(shí)才考慮鄰接表加 Dijkstra 堆優(yōu)化那是另一個(gè)故事。2.3 文件存儲(chǔ)與加載city.txt 和 route.txt 的約定數(shù)據(jù)不能寫死在代碼里這是課設(shè)評(píng)分的重要觀察點(diǎn)。用兩個(gè)文本文件分別存城市和線路將來替換數(shù)據(jù)就能模擬不同區(qū)域系統(tǒng)就不只是“全國”換成任意網(wǎng)絡(luò)都能跑。城市文件每行一個(gè)城市線路文件每行一條邊格式越簡單越好。我用兩個(gè)文件city.txt 存城市編號(hào)和名字route.txt 存邊的兩個(gè)端點(diǎn)和權(quán)重。下面這個(gè)表格是字段約定文件字段說明示例city.txtid 城市名城市編號(hào)從 0 開始城市名單詞間不要有空格0 A市route.txt起點(diǎn) 終點(diǎn) 權(quán)重權(quán)重表示距離或時(shí)間整數(shù)0 2 10加載函數(shù)分開寫先讀城市再讀線路。線路加載前必須把鄰接矩陣初始化成全 INF對(duì)角線初始化為 0否則程序會(huì)拿著內(nèi)存里的殘留值當(dāng)距離算。int loadCities(const char* path) { FILE* fp fopen(path, r); if (!fp) { printf(無法打開城市文件: %s\n, path); return -1; } g_graph.n 0; while (fscanf(fp, %d %63s, g_graph.cities[g_graph.n].id, g_graph.cities[g_graph.n].name) 2) { g_graph.n; } fclose(fp); return g_graph.n; } void loadRoutes(const char* path) { for (int i 0; i MAX_CITY; i) { for (int j 0; j MAX_CITY; j) { g_graph.edge[i][j] (i j) ? 0 : INF; } } FILE* fp fopen(path, r); if (!fp) { printf(無法打開線路文件: %s\n, path); return; } int u, v, w; while (fscanf(fp, %d %d %d, u, v, w) 3) { if (u MAX_CITY || v MAX_CITY) continue; g_graph.edge[u][v] w; g_graph.edge[v][u] w; // 無向圖對(duì)稱寫入 } fclose(fp); }fscanf 的 %63s 限制了城市名長度避免一個(gè)超長名字把緩沖區(qū)寫穿。 2 和 3 的判斷很關(guān)鍵它表示“每行必須完整讀到對(duì)應(yīng)數(shù)量的字段才算一條有效數(shù)據(jù)”空行和壞行會(huì)被跳過而不是讓程序崩潰。加載線路前重置 n 和鄰接矩陣是重復(fù)加載數(shù)據(jù)的后悔藥程序支持重新載入文件時(shí)不會(huì)越界。2.4 初始化細(xì)節(jié)INF 的值為什么不能拍腦袋鄰接矩陣初始化時(shí)不可達(dá)邊用什么值看似小事實(shí)際是課設(shè)翻車重災(zāi)區(qū)。用 0 肯定不行0 會(huì)被當(dāng)成一條零代價(jià)路徑Dijkstra 一跑全是 0。用 INT_MAX 也不行松弛比較 dist[u] w 時(shí)兩個(gè)大數(shù)相加直接溢出成負(fù)數(shù)結(jié)果比任何路徑都小算法全亂。我在代碼里統(tǒng)一用 1e9 作為 INF。城市數(shù) 256邊權(quán)就算到十萬dist[u] w 撐死幾千萬離 int 上限還遠(yuǎn)。這個(gè)值既大得足夠表示“不可達(dá)”又小得不會(huì)溢出是面試和課設(shè)里最穩(wěn)的選擇。如果你手癢想用 2147483647那要么在松弛前判 w INF要么改成 long long否則遲早被溢出坑一次。3. 核心算法Dijkstra 與 Floyd 的選型、實(shí)現(xiàn)和參數(shù)3.1 選型判斷單點(diǎn)查詢用 Dijkstra全源預(yù)計(jì)算用 Floyd交通咨詢系統(tǒng)最常見的需求是“查 A 到 B 的最短路”。單次查詢用 Dijkstra時(shí)間復(fù)雜度 O(n2)簡單直接。如果系統(tǒng)需要頻繁查詢?nèi)我鈨沙鞘兄g的最短路每次跑 Dijkstra 就會(huì)重復(fù)計(jì)算這時(shí)候應(yīng)該上 Floyd一次性求出所有點(diǎn)對(duì)的最短路后續(xù)每次查詢 O(1) 取結(jié)果。課設(shè)里的選擇標(biāo)準(zhǔn)我總結(jié)成一句話菜單只有單次查詢Dijkstra 就夠了菜單有“任意兩地查詢”且城市數(shù)不超過 200Floyd 更省事代碼只有三層循環(huán)。有些同學(xué)兩個(gè)都寫了答辯時(shí)反而要解釋兩套代碼的行為差異沒必要。我一般用 Dijkstra 做單次查詢換乘查詢用 BFS各司其職。3.2 Dijkstra 模板鄰接矩陣版的最短路與路徑記錄Dijkstra 的教材實(shí)現(xiàn)到處都是但很多版本只返回距離不返回路徑。課設(shè)里如果沒有路徑查完只會(huì)輸出一個(gè)數(shù)字根本沒法演示。所以我寫的模板把路徑也記錄下來用 prev 數(shù)組存每個(gè)節(jié)點(diǎn)的前驅(qū)最后從終點(diǎn)回溯到起點(diǎn)。void dijkstra(int start, int dest, int* dist, int* prev, int* path, int* pathLen) { int visited[MAX_CITY] {0}; for (int i 0; i g_graph.n; i) { dist[i] g_graph.edge[start][i]; prev[i] (dist[i] ! INF i ! start) ? start : -1; } visited[start] 1; dist[start] 0; prev[start] -1; // 起點(diǎn)沒有前驅(qū)回溯到此停止 for (int step 1; step g_graph.n; step) { int u -1; int minDist INF; for (int i 0; i g_graph.n; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; // 剩余節(jié)點(diǎn)不可達(dá)提前結(jié)束 visited[u] 1; for (int v 0; v g_graph.n; v) { if (!visited[v] g_graph.edge[u][v] ! INF dist[u] g_graph.edge[u][v] dist[v]) { dist[v] dist[u] g_graph.edge[u][v]; prev[v] u; } } } *pathLen 0; if (dist[dest] INF) return; for (int cur dest; cur ! -1; cur prev[cur]) { path[(*pathLen)] cur; if (cur start) break; } for (int i 0; i *pathLen / 2; i) { int tmp path[i]; path[i] path[*pathLen - 1 - i]; path[*pathLen - 1 - i] tmp; } }代碼第 7 行給所有點(diǎn)初始化了“通過起點(diǎn)直接能到的前驅(qū)”這個(gè)動(dòng)作很多模板會(huì)漏。如果不初始化回溯路徑時(shí) prev 是野值輕則路徑錯(cuò)亂重則死循環(huán)。每輪選最小未訪問節(jié)點(diǎn)用線性掃描城市數(shù)量幾百時(shí)完全夠用。松弛的判斷條件是dist[u] edge[u][v] dist[v]這里要求 edge 不為 INF防止把“不可達(dá)”加成“可達(dá)”。3.3 最少換乘不是“權(quán)重小一點(diǎn)”是另一張圖上的 BFS最短距離和最少換乘經(jīng)常被混為一談。距離最短的路徑要經(jīng)過三個(gè)城市、換兩次車換乘最少的路徑可能是直連但繞遠(yuǎn)路。兩個(gè)指標(biāo)本質(zhì)不同不能用同一套權(quán)重。最少換乘問題的標(biāo)準(zhǔn)做法是把每條邊權(quán)重視為 1跑無權(quán)圖的最短路徑BFS 就是最優(yōu)解。換乘次數(shù)等于“經(jīng)過的邊數(shù) ? 1”直連線路是 1 條邊換乘 0 次。int minTransfers(int start, int dest) { int queue[MAX_CITY], head 0, tail 0; int step[MAX_CITY]; for (int i 0; i g_graph.n; i) step[i] -1; step[start] 0; queue[tail] start; while (head tail) { int u queue[head]; if (u dest) break; for (int v 0; v g_graph.n; v) { if (g_graph.edge[u][v] ! INF step[v] -1) { step[v] step[u] 1; queue[tail] v; } } } if (step[dest] -1) return -1; // 不可達(dá) if (step[dest] 0) return 0; // 起點(diǎn)就是終點(diǎn) return step[dest] - 1; // 邊數(shù)減一 }step 數(shù)組記錄從起點(diǎn)到每個(gè)點(diǎn)經(jīng)過的邊數(shù)同時(shí)兼作 visited 標(biāo)記。這里必須用 BFS 而不是 DFS因?yàn)?BFS 第一次到達(dá)某個(gè)點(diǎn)時(shí)就是最短邊數(shù)DFS 會(huì)繞路。如果題目里所謂“換乘”指換乘交通工具類型比如高鐵轉(zhuǎn)飛機(jī)那要建“線路圖”而不是“城市圖”頂點(diǎn)變成車次兩個(gè)車次有共同城市才連邊那是進(jìn)階版本課設(shè)一般用不到。3.4 參數(shù)與邊界不可達(dá)節(jié)點(diǎn)、起點(diǎn)終點(diǎn)相同、負(fù)權(quán)邊Dijkstra 的適用前提是邊權(quán)非負(fù)。交通網(wǎng)絡(luò)里的距離、時(shí)間、票價(jià)天然非負(fù)所以放心用。但如果自己擴(kuò)展系統(tǒng)時(shí)允許“臨時(shí)優(yōu)惠”“反向里程”之類負(fù)數(shù)權(quán)重Dijkstra 會(huì)給出錯(cuò)誤結(jié)果那就要換算法。課設(shè)文檔里寫一句“本系統(tǒng)交通場(chǎng)景均為非負(fù)權(quán)值故采用 Dijkstra”是很好的邊界說明。不可達(dá)的情況也要處理。dijkstra 結(jié)束后如果 dist[dest] 還是 INF不能給用戶輸出 0要提示“暫無可達(dá)路徑”。起點(diǎn)和終點(diǎn)相同的查詢直接返回 0 和只含一個(gè)頂點(diǎn)的路徑。這些細(xì)節(jié)在答辯演示時(shí)容易被老師專門問到提前擋住。4. 從算法到系統(tǒng)菜單交互、結(jié)果展示和一組可信的自測(cè)數(shù)據(jù)4.1 菜單狀態(tài)機(jī)用 while switch 把查詢串成一個(gè)系統(tǒng)算法寫好了還得有一個(gè)讓用戶操作的殼。課程設(shè)計(jì)系統(tǒng)不需要圖形界面命令行菜單就夠。一個(gè)死循環(huán)加用戶輸入通過 switch 分發(fā)到不同功能退出時(shí)用 break 跳出這個(gè)結(jié)構(gòu)既簡單又好解釋。void runMenu() { int choice -1; while (choice ! 0) { printf(\n 全國交通出行咨詢模擬系統(tǒng) \n); printf(1. 查詢兩地最短距離\n); printf(2. 查詢兩地最少換乘\n); printf(3. 查看所有城市列表\n); printf(0. 退出系統(tǒng)\n); printf(請(qǐng)選擇功能: ); if (scanf(%d, choice) ! 1) { printf(輸入無效請(qǐng)重新選擇\n); while (getchar() ! \n); // 清空輸入緩沖 choice -1; continue; } switch (choice) { case 1: queryShortestPath(); break; case 2: queryMinTransfer(); break; case 3: listAllCities(); break; case 0: printf(感謝使用再見\n); break; default: printf(沒有該選項(xiàng)\n); break; } } }輸入無效時(shí)用 getchar 把緩沖區(qū)的殘留字符讀完這是命令行程序的常規(guī)血淚處理。如果不做清理用戶隨便敲一個(gè)字母scanf 失敗后無限循環(huán)刷屏演示時(shí)相當(dāng)尷尬。菜單層級(jí)也不要做得太深一兩層正好太深老師操作起來會(huì)覺得系統(tǒng)不好用。4.2 路徑回溯與格式化輸出把數(shù)組變成“A市 - C市 - D市 - B市”Dijkstra 算出的 path 數(shù)組存的是節(jié)點(diǎn)下標(biāo)直接打印數(shù)字沒人能看懂。輸出前要映射回城市名并按順序拼接成一條完整路徑。路徑在回溯階段是從終點(diǎn)倒著存進(jìn)數(shù)組的所以要先翻轉(zhuǎn)再逐段輸出。void printPath(int* path, int pathLen) { if (pathLen 0) { printf(暫無可達(dá)路徑\n); return; } for (int i 0; i pathLen; i) { if (i 0) printf( - ); printf(%s, g_graph.cities[path[i]].name); } printf(\n); } void queryShortestPath() { int from, to, dist[MAX_CITY], prev[MAX_CITY]; int path[MAX_CITY], pathLen; printf(請(qǐng)輸入起點(diǎn)城市編號(hào): ); scanf(%d, from); printf(請(qǐng)輸入終點(diǎn)城市編號(hào): ); scanf(%d, to); if (from 0 || from g_graph.n || to 0 || to g_graph.n) { printf(城市編號(hào)越界\n); return; } if (from to) { printf(起點(diǎn)和終點(diǎn)相同距離為 0\n); return; } dijkstra(from, to, dist, prev, path, pathLen); if (dist[to] INF) { printf(暫無可達(dá)路徑\n); return; } printf(最短距離: %d\n, dist[to]); printf(路徑方案: ); printPath(path, pathLen); }城市編號(hào)越界、起終點(diǎn)相同、不可達(dá)三種情況都在用戶輸入層攔截算法層不用重復(fù)操心。輸出格式保持一致先給距離再給路徑這是最直觀的展示順序。4.3 我用來驗(yàn)證算法的 5 節(jié)點(diǎn)樣本數(shù)據(jù)寫完算法最怕自我感覺良好隨手填幾組數(shù)據(jù)全是直連算法再錯(cuò)也看不出來。我習(xí)慣準(zhǔn)備一個(gè) 5 節(jié)點(diǎn)的小樣本故意設(shè)計(jì)一條“距離最短但換乘多”的路徑和一條“直連但距離遠(yuǎn)”的路徑用來同時(shí)驗(yàn)證 Dijkstra 和換乘 BFS 是否各司其職。city.txt0 A市 1 B市 2 C市 3 D市 4 E市route.txt0 2 10 2 3 20 3 1 30 0 1 100 0 4 50 4 1 5這張圖里A 到 B 有直連路線代價(jià) 100經(jīng)過 C、D 繞行的代價(jià)是 60經(jīng)過 E 的路線代價(jià) 55距離最短。換乘方面直連只要乘坐 1 段換乘 0 次經(jīng)過 E 要乘坐 2 段換乘 1 次經(jīng)過 C、D 要乘坐 3 段換乘 2 次。三個(gè)方案的排名完全不同正好測(cè)試系統(tǒng)區(qū)分兩個(gè)查詢目標(biāo)的能力。查詢預(yù)期結(jié)果最優(yōu)路徑A 到 B 最短距離55A市 - E市 - B市A 到 B 最少換乘0 次A市 - B市如果程序跑出來的最短距離是 60 或 100說明 Dijkstra 有 bug如果換乘查詢返回 1 次說明 BFS 把“經(jīng)過邊數(shù)”和“換乘次數(shù)”算混了。用這 5 條邊、6 條數(shù)據(jù)就能把兩套核心邏輯全部覆蓋比寫幾十個(gè)城市更有效率。5. 避坑指南從編譯通過到答案正確中間藏著這些坑5.1 數(shù)據(jù)讀入與初始化階段三個(gè)繞不開的問題**現(xiàn)象**路徑回溯時(shí)程序卡死或者打印出來的路徑在幾個(gè)城市之間來回循環(huán)最后棧溢出。 **原因**城市編號(hào)基準(zhǔn)不統(tǒng)一。城市文件里編號(hào)從 1 開始數(shù)組下標(biāo)從 0 開始Dijkstra 里一邊用數(shù)組下標(biāo)一邊用文件編號(hào)prev 數(shù)組里存的是舊編號(hào)回溯時(shí)找不到起點(diǎn)甚至形成環(huán)。 **解決**統(tǒng)一用數(shù)組下標(biāo)。文件里讀出 id 后存成 id-1或者要求文件編號(hào)從 0 開始我直接采用后者。只要代碼里出現(xiàn)“城市編號(hào) ? 1”這種神秘代碼就說明基準(zhǔn)又混了。**現(xiàn)象**城市名讀出來是亂碼或者最后一個(gè)字消失。 **原因**源碼文件、數(shù)據(jù)文件、控制臺(tái)三者的編碼不一致。Windows 下編譯器默認(rèn)用 GBK 存源碼文本編輯器卻把 city.txt 存成了 UTF-8控制臺(tái)按 GBK 解碼自然亂碼。 **解決**把數(shù)據(jù)文件一律另存為與源碼相同的編碼。Windows 下統(tǒng)一 GBKLinux/macOS 下統(tǒng)一 UTF-8。寫文檔時(shí)附一句“數(shù)據(jù)文件需與源碼編碼保持一致”能省掉演示前最后一分鐘的手忙腳亂。**現(xiàn)象**大邊權(quán)時(shí)程序輸出負(fù)數(shù)距離路徑完全錯(cuò)亂。 **原因**INF 初始化為 INT_MAX松弛比較時(shí)執(zhí)行 dist[u] edge[u][v]兩個(gè)值相加溢出為負(fù)每次更新都被當(dāng)成更短路徑。 **解決**INF 用 1e9不要用 INT_MAX?；蛘甙阉芯嚯x變量改成 long long但那樣打印格式又要調(diào)。最簡單就是固定 1e9省心。5.2 算法與輸出階段兩個(gè)容易被當(dāng)成玄學(xué)的錯(cuò)誤**現(xiàn)象**Floyd 三層循環(huán)寫完后部分點(diǎn)對(duì)結(jié)果正確部分錯(cuò)誤而且錯(cuò)誤還“看起來挺對(duì)”。 **原因**循環(huán)順序把 k 寫到了最內(nèi)層。Floyd 的中間節(jié)點(diǎn) k 必須放在最外層才能保證每次用到的 dist[i][k] 和 dist[k][j] 已經(jīng)包含了前 k-1 個(gè)中間節(jié)點(diǎn)的更新結(jié)果。順序錯(cuò)了松弛狀態(tài)會(huì)互相污染。 **解決**牢記標(biāo)準(zhǔn)順序k 在最外i 次之j 最內(nèi)。寫代碼時(shí)先寫循環(huán)框架再填決策不要邊寫邊調(diào)順序。**現(xiàn)象**Dijkstra 輸出的距離正確但路徑方向反了終點(diǎn)在前、起點(diǎn)在后。 **原因**回溯時(shí)從終點(diǎn)一路往 prev 找路徑自然是從終點(diǎn)倒著收集的。忘了翻轉(zhuǎn)數(shù)組直接打印就成了 A 市在前面。這一條不算復(fù)雜但幾乎每屆課設(shè)都有同學(xué)中招屬于典型的手滑問題。 **解決**回溯完成后對(duì)半翻轉(zhuǎn)數(shù)組或者在收集時(shí)從起點(diǎn)向終點(diǎn)遞歸。翻轉(zhuǎn)代碼只有三行寫在 dijkstra 函數(shù)末尾統(tǒng)一處理不要在 printPath 里翻避免查詢函數(shù)多得時(shí)候漏掉。**現(xiàn)象**第二次加載數(shù)據(jù)文件時(shí)程序崩潰城市數(shù)量翻倍增長。 **原因**loadCities 里 n 從上次的值開始繼續(xù)累加城市數(shù)組越界或者舊數(shù)據(jù)殘留干擾新數(shù)據(jù)。 **解決**每次加載前先把 g_graph.n 置 0鄰接矩陣在 loadRoutes 里重新初始化。重復(fù)加載本就是課設(shè)加分項(xiàng)但前提是狀態(tài)干凈。我習(xí)慣在文件讀取模塊提供 resetGraph 函數(shù)加載前統(tǒng)一調(diào)用。6. 答辯前還能做什么驗(yàn)證習(xí)慣、擴(kuò)展方向與怎么講清楚6.1 先跑通 5 節(jié)點(diǎn)最小樣例再上全國數(shù)據(jù)我自己的習(xí)慣是數(shù)據(jù)從小往大加。先用第 4 章的 5 節(jié)點(diǎn)數(shù)據(jù)把所有功能跑通確認(rèn)輸出與手算一致再替換成幾十個(gè)城市的大文件。這樣做的好處是出錯(cuò)時(shí)縮圈容易5 個(gè)節(jié)點(diǎn)都能手推答案算法對(duì)沒對(duì)一眼就知道直接上大數(shù)據(jù)錯(cuò)了根本不知道正確答案是什么。6.2 三個(gè)低成本高分?jǐn)U展時(shí)間權(quán)重、換乘限制、線路維護(hù)第一個(gè)擴(kuò)展是給系統(tǒng)加第二套邊權(quán)距離和時(shí)間各存一個(gè)矩陣查詢時(shí)讓用戶選擇“按距離”還是“按時(shí)間”Dijkstra 函數(shù)提取對(duì)應(yīng)矩陣邏輯不用改。第二個(gè)擴(kuò)展是限定“最多換乘 N 次”BFS 里加一層深度判斷超過 N 就剪掉。第三個(gè)擴(kuò)展是“新增/刪除一條線路”提供菜單入口修改鄰接矩陣并重新持久化到 route.txt這能讓系統(tǒng)從“只讀查詢”變成“可維護(hù)系統(tǒng)”。6.3 答辯怎么講把圖論價(jià)值講清楚答辯時(shí)不要上來就講代碼行數(shù)老師想聽的是建模思想。我一般這樣講把全國交通網(wǎng)抽象成無向帶權(quán)圖城市是頂點(diǎn)線路是帶權(quán)邊最短距離用 Dijkstra核心是貪心加松弛最少換乘把權(quán)重置為 1用 BFS 求最少的邊數(shù)。把這三句話說清楚比背十段代碼都管用。另外一定要現(xiàn)場(chǎng)演示一次不可達(dá)查詢讓系統(tǒng)輸出友好提示這個(gè)場(chǎng)景比正常查詢更能體現(xiàn)邊界處理意識(shí)。這套方案做完我最大的教訓(xùn)就是數(shù)據(jù)初始化和編號(hào)基準(zhǔn)比算法本身更容易翻車。算法只需要理解數(shù)據(jù)問題需要排查而且排查起來毫無成就感。所以現(xiàn)在每寫一個(gè)查詢模塊我都先用小樣本跑通再擴(kuò)數(shù)據(jù)這個(gè)習(xí)慣讓我少熬了很多夜。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取