VC++ 火車票訂票系統里程計算演算法：圖論權值與線性表實作

問題建模：里程即圖的邊權重

火車路網本質是一個有向加權圖：

• 頂點：車站。
• 邊：區間列車。
• 權重：兩站間里程（公里數）。

資料結構選型：鄰接表 (線性表實作)

適合稀疏圖（車站多、直達區間少），空間效率高。

// 邊節點：代表一個直達區間
struct EdgeNode {
    int destStationId;    // 終點站 ID
    int distance;         // 里程 (權重)
    int trainId;          // 列車班次
    EdgeNode* next;       // 同起點的下一條邊
};

// 頂點節點：代表一個車站
struct VertexNode {
    int stationId;
    char stationName[32];
    EdgeNode* firstEdge;  // 指向第一條出發邊
};

// 圖結構：車站陣列
struct Graph {
    VertexNode stations[MAX_STATIONS];
    int stationCount;
};

里程計算演算法

情境 A：查詢指定路徑的總里程 (已知經過站序列)

int calculateTotalDistance(Graph* g, int path[], int pathLen) {
    int total = 0;
    for (int i = 0; i < pathLen - 1; i++) {
        int u = path[i];
        int v = path[i+1];
        // 遍歷 u 的鄰接表找到指向 v 的邊
        EdgeNode* e = g->stations[u].firstEdge;
        while (e && e->destStationId != v) e = e->next;
        if (!e) return -1; // 路徑不存在
        total += e->distance;
    }
    return total;
}

情境 B：查詢兩站間「最短里程」路徑 (戴克斯特拉演算法)

若需求是「自動推薦最短里程路線」，需實作 Dijkstra：

// 優先隊列節點
struct PQNode {
    int stationId;
    int dist; // 從起點累積里程
    bool operator<(const PQNode& other) const { return dist > other.dist; } // 小根堆
};

vector dijkstra(Graph* g, int src, int dest) {
    vector dist(g->stationCount, INT_MAX);
    vector prev(g->stationCount, -1);
    priority_queue pq;
    
    dist[src] = 0;
    pq.push({src, 0});
    
    while (!pq.empty()) {
        int u = pq.top().stationId; pq.pop();
        if (u == dest) break;
        
        for (EdgeNode* e = g->stations[u].firstEdge; e; e = e->next) {
            int v = e->destStationId;
            int alt = dist[u] + e->distance;
            if (alt < dist[v]) {
                dist[v] = alt;
                prev[v] = u;
                pq.push({v, alt});
            }
        }
    }
    
    // 重構路徑
    vector path;
    for (int cur = dest; cur != -1; cur = prev[cur]) path.push_back(cur);
    reverse(path.begin(), path.end());
    return path; // 空向量表示不可達
}

系統整合建議

1. 資料來源：里程資料建議存於資料庫 (SQLite/MySQL)，啟動時載入建圖，或使用記憶體映射檔快速反序列化。
2. 快取策略：熱門區間 (如北上廣深) 最短路徑可預計算快取。
3. 擴充性：權重欄位可擴充為結構體，包含 時間、票價、列車類型，支援多條件最優路徑查詢。