最優(yōu)路徑算法

解決方案一:Dijkstra算法(單源最短路徑)單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)該性質(zhì)描述為：如果P(i,j)={Vi.…Vk..Vs…Vj}是從頂點i至叮的最短路徑，k和s是這條路徑上的一個中間頂點，那么P(k,s)必定是從k到s的最短路徑。下面證明該性質(zhì)的正確性。假設(shè)P(i,j)={Vi....Vk..Vs...Vj}是從頂點i至叮的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)vP(i,j)。則與P(i,j)是從i至叮的最短路徑相矛盾。因此該性質(zhì)得證。Dijkstra算法由上述性質(zhì)可知，如果存在一條從i至叮的最短路徑(Vi..…Vk,Vj)，Vk是Vj前面的一頂點。那么(Vi...Vk)也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點V0,首先選擇其直接相鄰的頂點中長度最短的頂點Vi,那么當(dāng)前已知可得從VO到達Vj頂點的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據(jù)這種思路，假設(shè)存在G=vV,E＞，源頂點為VO,U={VO},dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點。從V-U中選擇使dist[i]值最小的頂點i,將i加入到U中；更新與i直接相鄰頂點的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})知道U=V,停止。測試數(shù)據(jù):60100606010060運行結(jié)果:7010S020ltj007?02007010S020ltj007?0200解決方案2ArcGISforAndroid査找最短路徑ArcGISforAndroid(10.1.1)只支持在線的網(wǎng)絡(luò)分析，執(zhí)行路徑分析可以通過RoutingTask類的solve方法來進行，通過給slove方法傳遞RoutingParameters類型的參數(shù)，可以最短路徑的查找。而要成功執(zhí)行路徑分析，就必須發(fā)布網(wǎng)絡(luò)分析服務(wù)，比較麻煩，下面的代碼中使用的服務(wù)是arcgisonline.上已經(jīng)發(fā)布的服務(wù)。以下代碼程序的界面如下：

界面包含兩控件：Textview和MapView,在執(zhí)行路徑分析前單擊MapView會增加路徑分析的?？奎c，長按MapView會根據(jù)?？奎c（至少要兩個停靠點）執(zhí)行查找最短路徑的操作,執(zhí)行成功之后會在Textview中顯示相關(guān)的路徑信息，這時候單擊查詢的路徑，會選中路徑片段，相關(guān)的信息也會在TextView上顯示。單擊TextView就會清空所有結(jié)果，恢復(fù)到原始狀態(tài)。結(jié)果