改進的時延約束Steiner樹算法

徐劍　倪宏　鄧浩江　劉磊

摘要：針對現有時延約束steiner樹算法時間復雜度較高以及生成的組播樹代價較高的問題，提出了一種改進的時延約束Steiner樹算法。該算法采用DIjkstra算法路徑遞增的基本思想和鏈路共享的方法，在快速搜索階段，依次搜索到當前樹有最小可行代價的節點，將目的節點通過最小可行代價路徑加入組播樹；在異常處理階段，將遺漏的目的節點通過最小時延路徑加入組播樹，進而生成滿足時延約束的Steiner樹。理論分析和實驗結果表明，與同類算法相比，該算法能夠以較低的時間復雜度，取得較好的組播樹代價。

關鍵詞：Steiner樹；代價；時延約束；路徑遞增；鏈路共享