萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C++ 戴克斯特拉演算法實作最短路徑查詢系統

問題定義

給定無向加權圖 (景點節點、路徑邊、距離權重),查詢任兩點間最短路徑長度與實際路徑節點序列。本文實作完整的主控台導航系統,包含:

  • 圖資料結構 (鄰接矩陣)
  • 檔案載入/手動建圖
  • Dijkstra 演算法 (含路徑重建)
  • 互動式選單

資料結構定義

#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;
};

Dijkstra 核心演算法

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());
}

檔案 I/O (二進位格式)

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
路徑輸出僅節點名可輸出距離、轉彎指示、預估時間

現代 C++ 重構要點

  • 使用 std::vector, std::string, std::optional 替代原始陣列/指標。
  • 封裝為 class NavigationSystem,分離 UI、資料、演算法。
  • 單元測試覆蓋:空圖、單節點、無路徑、多條等長最短路徑。
  • 序列化改用 JSON/Protobuf 取代二進位,利於跨語言與除錯。
copyright © 萬盛學電腦網 all rights reserved