路線規劃核心演算法實作

智慧導航與使用者體驗的革命

對於任何一款大眾運輸導航應用程式而言，路線規劃功能都是其不可撼動的靈魂核心。在本次的重大系統更新中，我們正式上線了自主研發的路線規劃核心演算法模組（內部代號為 hrroutes.js）。這項全新底層功能的加入，為我們的產品帶來了革命性的使用者體驗（UX）提升。過去，使用者可能需要自行對照複雜的捷運路線圖，在腦海中拼湊轉乘方案；現在，只需在搜尋介面上輕觸起點與終點站，系統便能在眨眼之間運算出最佳行車路徑。

更重要的是，我們的演算法不僅僅是找出一條能通行的路，它還綜合考量了整體乘車時間，並將「轉乘次數最小化」納入權重計算中，致力於為使用者提供最直覺、最省力的通勤建議。當結果在毫秒間呈現在螢幕上時，使用者能感受到無與倫比的流暢與可靠性。

演算法開發的深淵：踩坑記錄

然而，在實作這個看似標準的圖論（Graph Theory）路徑尋找問題時，我卻在演算法的架構設計上跌了一大跤。在開發初期，由於考量到程式碼撰寫的簡潔性與直觀度，我選擇了使用遞迴（Recursion）的方式來實作深度優先搜尋（Depth-First Search, DFS），以此來嘗試窮舉所有可能的路線，並從中篩選出最短的一條。在小規模的單點測試資料（例如僅包含單一條捷運線的節點）上，這個遞迴演算法運作得非常完美且迅速。

但這個隱藏的「坑」在我們正式匯入完整且複雜的路網拓撲資料後，徹底爆發了。真實世界的大眾運輸路網充滿了環狀線、多線交會站以及錯綜複雜的雙向連結，這使得整個資料結構變成了一個高度循環的圖（Cyclic Graph）。當我嘗試進行跨越多條路線的長途行程規劃測試時，遞迴函式在處理交會節點時失去了方向，陷入了近乎無限的深度呼叫中。這不僅導致了極長的運算等待時間，更慘的是，瀏覽器的 JavaScript 引擎很快就耗盡了記憶體，拋出了 Maximum call stack size exceeded 的致命錯誤。這導致整個應用程式當機崩潰，使用者看到的不是規劃好的路線，而是一片死寂的白屏。

邏輯重構與迭代式廣度優先搜尋

為了解決這個災難性的崩潰問題，我必須重新審視圖論演算法的本質。深度優先搜尋在尋找無權重圖的最短路徑時，本來就不是一個明智的選擇，因為它可能會先鑽進一條極其漫長的遠路。加上遞迴所帶來的 Call Stack 記憶體負擔，更是讓情況雪上加霜。我利用除錯器（Debugger）單步執行，觀察到在密集的交會站節點上，遞迴路徑產生了指數級的爆炸增長。

痛定思痛後，我決定將核心演算法從遞迴的 DFS 徹底重寫為迭代（Iterative）的廣度優先搜尋（Breadth-First Search, BFS）。BFS 的運作特性使其能夠像水波一樣，由起點逐層向外擴展。這個特性在數學上保證了，當我們第一次觸碰到終點站時，所走過的路徑必定是站數最少的最短路徑。更重要的是，我引入了佇列（Queue）資料結構來管理待處理的節點，並嚴格使用一個 Set 來精確記錄已經拜訪過的車站，從根本上避免了重複走訪與無限迴圈的問題。改為迭代方式後，所有的運算都在 Heap 記憶體中安全地進行，徹底消除了 Call Stack 溢出的風險。現在，即便是面對最複雜的跨線轉乘規劃，系統也能展現出極致的效能與絕對的穩定性。

function findRouteDFS(currentStation, endStation, visited, path) {
    visited.add(currentStation);
    path.push(currentStation);
    
    if (currentStation === endStation) return path;

    const neighbors = graph.get(currentStation);
    for (let neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            // 危險的遞迴呼叫：在複雜交會網中極易導致 
            // Call Stack Overflow (堆疊溢位) 崩潰
            const result = findRouteDFS(
                neighbor, endStation, visited, [...path]
            );
            if (result) return result;
        }
    }
    return null;
}

function findRouteBFS(startStation, endStation) {
    const queue = [[startStation]];
    const visited = new Set([startStation]);

    while (queue.length > 0) {
        // 迭代方式：利用佇列與迴圈取代遞迴，確保記憶體安全
        const path = queue.shift();
        const currentStation = path[path.length - 1];

        if (currentStation === endStation) return path;

        const neighbors = graph.get(currentStation);
        for (let neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor); // 確實標記已拜訪節點
                queue.push([...path, neighbor]);
            }
        }
    }
    return null; // 若無法抵達則回傳空值
}