給定無向加權圖 (景點節點、路徑邊、距離權重),查詢任兩點間最短路徑長度與實際路徑節點序列。本文實作完整的主控台導航系統,包含:
#include
#include
#include
#include
#include
#include
const int MAX_V = 20;
const int INF = INT_MAX / 2;
struct Spot {
char name[11]; // 景點名稱 ≤10
char intro[21]; // 簡介 ≤20
};
struct Graph {
Spot spots[MAX_V];
int dist[MAX_V][MAX_V]; // 鄰接矩陣
int spotCount = 0;
int pathCount = 0;
};
struct PathInfo {
int length = INF;
int prev = -1; // 前驅節點索引
bool visited = false;
};
void dijkstra(const Graph& g, int src, int dest, std::vector& path, int& totalDist)
{
PathInfo info[MAX_V];
info[src].length = 0;
for (int iter = 0; iter < g.spotCount; ++iter)
{
// 1. 選擇未訪問且距離最小的節點
int u = -1;
int minDist = INF;
for (int i = 0; i < g.spotCount; ++i)
if (!info[i].visited && info[i].length < minDist)
minDist = info[u = i].length;
if (u == -1 || u == dest) break; // 無路徑或已達終點
info[u].visited = true;
// 2. 鬆弛鄰邊
for (int v = 0; v < g.spotCount; ++v)
{
if (!info[v].visited && g.dist[u][v] < INF)
{
int alt = info[u].length + g.dist[u][v];
if (alt < info[v].length)
{
info[v].length = alt;
info[v].prev = u;
}
}
}
}
// 3. 重建路徑
totalDist = info[dest].length;
if (totalDist >= INF) { path.clear(); return; }
for (int cur = dest; cur != -1; cur = info[cur].prev)
path.push_back(cur);
std::reverse(path.begin(), path.end());
}
bool loadSpots(Graph& g, const char* filename)
{
std::ifstream in(filename, std::ios::binary);
if (!in) return false;
in.read(reinterpret_cast(&g.spotCount), sizeof(int));
for (int i = 0; i < g.spotCount; ++i)
{
in.read(g.spots[i].name, 10);
in.read(g.spots[i].intro, 20);
}
return true;
}
bool loadPaths(Graph& g, const char* filename)
{
std::ifstream in(filename, std::ios::binary);
if (!in) return false;
in.read(reinterpret_cast(&g.pathCount), sizeof(int)); // 實際未使用,矩陣直接讀
for (int i = 0; i < g.spotCount; ++i)
for (int j = 0; j < g.spotCount; ++j)
in.read(reinterpret_cast(&g.dist[i][j]), sizeof(int));
return true;
}
void saveGraph(const Graph& g, const char* spotsFile, const char* pathsFile)
{
std::ofstream out1(spotsFile, std::ios::binary);
out1.write(reinterpret_cast(&g.spotCount), sizeof(int));
for (int i = 0; i < g.spotCount; ++i)
{
out1.write(g.spots[i].name, 10);
out1.write(g.spots[i].intro, 20);
}
std::ofstream out2(pathsFile, std::ios::binary);
out2.write(reinterpret_cast(&g.pathCount), sizeof(int));
for (int i = 0; i < g.spotCount; ++i)
for (int j = 0; j < g.spotCount; ++j)
out2.write(reinterpret_cast(&g.dist[i][j]), sizeof(int));
}
int findSpotIndex(const Graph& g, const char* name)
{
for (int i = 0; i < g.spotCount; ++i)
if (std::strcmp(g.spots[i].name, name) == 0) return i;
return -1;
}
void queryShortestPath(Graph& g)
{
char sName[11], tName[11];
std::cout << "起點: "; std::cin.getline(sName, 11);
std::cout << "終點: "; std::cin.getline(tName, 11);
int s = findSpotIndex(g, sName);
int t = findSpotIndex(g, tName);
if (s == -1 || t == -1) { std::cout << "景點不存在\n"; return; }
std::vector path;
int dist;
dijkstra(g, s, t, path, dist);
if (path.empty()) { std::cout << "無路徑\n"; return; }
std::cout << "最短距離: " << dist << "\n路徑: ";
for (size_t i = 0; i < path.size(); ++i)
{
std::cout << g.spots[path[i]].name;
if (i + 1 < path.size()) std::cout << " -> ";
}
std::cout << "\n";
}
int main()
{
Graph g;
const char* spotsFile = "D:\\spots.dat";
const char* pathsFile = "D:\\paths.dat";
while (true)
{
std::cout << "\n=== 導航系統 ===\n"
<< "0. 載入地圖\n1. 手動建圖\n2. 查詢最短路徑\n3. 退出\n選項: ";
int opt; std::cin >> opt; std::cin.ignore();
if (opt == 0) {
if (loadSpots(g, spotsFile) && loadPaths(g, pathsFile))
std::cout << "載入成功\n";
else std::cout << "載入失敗\n";
}
else if (opt == 1) {
// 手動建圖邏輯 (略,參考原始碼)
}
else if (opt == 2) {
queryShortestPath(g);
}
else if (opt == 3) break;
}
return 0;
}
| 項目 | 現狀 | 優化方向 |
|---|---|---|
| 時間複雜度 | O(V²) (鄰接矩陣 + 線性找最小) | 改用 priority_queue + 鄰接表 → O(E log V) |
| 空間複雜度 | O(V²) | 稀疏圖改用鄰接表 vector |
| 最大節點 | 20 (硬編碼) | 改用動態容器 vector |
| 路徑輸出 | 僅節點名 | 可輸出距離、轉彎指示、預估時間 |
std::vector, std::string, std::optional 替代原始陣列/指標。class NavigationSystem,分離 UI、資料、演算法。