[發明專利]一種直線優化的最短路徑搜索方法

有效

• 申請號: 200810246852.3
• 申請日: 2008-12-26
• 公開（公告）號: CN101447947A
• 公開（公告）日: 2009-06-03
• 發明（設計）人: 趙春江;王開義;張方田;劉忠強;隋靜;喻鋼
• 申請（專利權）人: 北京農業信息技術研究中心
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04W40/20;G06F17/30
• 代理公司: 北京路浩知識產權代理有限公司
• 代理人: 張國良

1.一種獲取兩地間最短路徑的方法，其特征在于，所述獲取兩地間最短路徑的方法包括步驟：?

S1，獲取兩地的起點、終點以及所述起點的相鄰點；?

S2，獲取所述相鄰點到起點之間的最短路徑距離；?

S3，獲取上述各相鄰點與終點之間的直線距離；?

S4，獲取上述最短路徑距離與直線距離之和的最小值以及取得該最小值的點；?

S5，判斷步驟S4中取得該最小值的點是否是終點，如果是，則獲取上述起點經所述取得該最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離；如果否，則獲取上述取得該最小值的點的所有相鄰點，然后轉步驟S2，其中用所述取得該最小值的點的相鄰點取代步驟S2中所述的相鄰點；?

所述步驟S5之前還包括：?

SA，判斷上述取得該最小值的點是否有相鄰點，如果否，則獲取上述起點經所述取得該最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離，如果是，則轉步驟SB；?

SB，判斷所述取得該最小值的點的相鄰點是否被選取作過最小值點，如果是，則獲取上述起點經所述取得該最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離，如果否，則轉步驟S2。?

2.如權利要求1所述的獲取兩地間最短路徑的方法，其特征在于，所述步驟S1中起點的相鄰點為與起點有路徑的點。?

3.一種獲取兩地間最短路徑的裝置，其特征在于，所述獲取兩地間最短路徑的裝置包括：?

輸入單元，用于輸入兩地的起點、終點以及所述起點的相鄰點；?

計算單元，與所述輸入單元相連，獲取上述各相鄰點到起點之間的最短路徑距離、上述各相鄰點與終點的直線距離；以及上述最短路徑距離與直線距離之和的最小值；

判斷單元，與所述計算單元相連，用于判斷使得起點與其所有相鄰點的最短路徑距離及所述起點的相鄰點與終點的直線距離之和取得最小值的點；判斷上述取得最小值的點是否有相鄰點，如果否，則獲取上述起點經所述取得最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離，如果是，則判斷所述取得最小值的點的相鄰點是否被選取作過最小值點，如果是，則獲取上述起點經所述取得最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離，如果否，則重新獲取使得距離之和達到最小值的點；判斷上述取得最小值的點是否是終點，如果是，則獲取上述起點經所述取得最小值的點到終點的路徑距離為起點與終點之間的最短路徑距離，如果否，則獲取上述取得最小值的點的所有相鄰點，并獲取這些相鄰點中能夠使距離之和達到最小值的點；

輸出單元，與所述判斷單元相連，用于輸出所述最短路徑距離。?