【文章內(nèi)容簡介】 , dk+lkj］，式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。3) 選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj 中最小的一個(gè)i：di=min［dj, 所有未標(biāo)記的點(diǎn)j］,點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。4) 找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前一點(diǎn),設(shè)置：i=j*。5) 標(biāo)記點(diǎn)i。如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2)再繼續(xù)。為了實(shí)現(xiàn)Dijkstra算法，在程序中首先引入三個(gè)類：class VERTEX //頂點(diǎn)類{public int id。public int Searched。 //0表示從來沒有搜索過，表示搜索過，但沒有完成，表示搜索完成，該點(diǎn)的最短路徑已經(jīng)找到public IPoint pPoint。public VERTEX Prev。public VERTEX Next。public Link Neighbor。//一個(gè)鏈接關(guān)系，相當(dāng)于線節(jié)點(diǎn)public double Weight。//權(quán)重，初始時(shí)置為無窮大，搜尋最短路徑時(shí)置為該點(diǎn)當(dāng)前最短路徑長度public VERTEX ShortPathPre。//在最短路徑上的前一個(gè)點(diǎn)public int LineID。//最短路徑中與前一個(gè)點(diǎn)之間的線的IDpublic SearchLink SLink。//Open或Close表中的鏈接}class Link//點(diǎn)的鄰接關(guān)系{public VERTEX v1。//每個(gè)Link對象的v1都應(yīng)該指向它所附屬的點(diǎn)節(jié)點(diǎn)public VERTEX v2。//每個(gè)Link對象的v2都應(yīng)該指向與它所附屬的點(diǎn)相鄰的那個(gè)點(diǎn)節(jié)點(diǎn)public double weight。//線的權(quán)重public Link v1Next。public Link v2Next。public int LineID。}class SearchLink//搜尋路徑時(shí)的鄰接關(guān)系，用來放入Open或Close表中{public VERTEX v。public SearchLink Prev。public SearchLink Next。}VERTEX類用來存儲點(diǎn)節(jié)點(diǎn)，Link類用來存儲鄰接關(guān)系，SearchLink是一個(gè)臨時(shí)的中間鄰接關(guān)系，在尋徑時(shí)替代VERTEX實(shí)例進(jìn)行運(yùn)算，用來維持鄰接多重表。系統(tǒng)的主要功能函數(shù)為：private VERTEX BuildTopo(IFeatureLayer pFeatLayerP,IFeatureLayer pFeatLayerL,IPoint pStartV,IPoint pEndV,ref int PointCount,ref intEdgeCount)，主要用來建立拓?fù)潢P(guān)系private void shortpath()，查詢最短路徑的主函數(shù)private void InsertOrder(SearchLink vIN,ref SearchLink vTO)按權(quán)重的升序插入private void Insert(SearchLink vIN,ref SearchLink vTO)插入private void Delete(ref SearchLink vOUT,ref SearchLink vFROM)從鏈表中刪除建立拓?fù)潢P(guān)系：VERTEX[]RoadNode=new VERTEX[NodeCount]。indexP=0。pFeatureP=()。while(null!=pFeatureP){indexP=(int)((ID))。if(indexP0){pFeatureP=()。continue。}RoadNode[indexP]=new VERTEX()。RoadNode[indexP].Neighbor=null。RoadNode[indexP].pPoint=(IPoint)。RoadNode[indexP].Searched=0。RoadNode[indexP].ShortPathPre=null。RoadNode[indexP].Weight=。pFeatureP=()。}首先建立VERTEX數(shù)組，用來存放點(diǎn)節(jié)點(diǎn)，在遍歷點(diǎn)層元素的過程中，根據(jù)點(diǎn)的ID號找到數(shù)組索引號，生成點(diǎn)節(jié)點(diǎn)的實(shí)例（即VERTEX實(shí)例）。建立這一過程的時(shí)間消耗與點(diǎn)的數(shù)量n成正比，即時(shí)間復(fù)雜度為O（n）。pFeatCsrL=(null,false)。int indexP1=0,indexP2=0。pFeatureL=()。while(null!=pFeatureL)//遍歷線對象，根據(jù)線的首尾節(jié)點(diǎn)ID，即點(diǎn)的索引，找到點(diǎn)，建立鏈接關(guān)系{t1++。tEdge++。vLink1=vLink2=null。pPointCol=(IPointCollection)。p1=(0)。p2=()。vWork=。flag1=flag2=0。indexP1=(int)((STNODEID))。indexP2=(int)((EDNODEID))。indexP=(int)((FID))。//依次獲得線元素的STNODEID、EDNODEID、FID三個(gè)字段的值vLink1=new Link()。=indexP。=(double)(int)((Weight))。=RoadNode[indexP1]。=RoadNode[indexP1].Neighbor。RoadNode[indexP1].Neighbor=vLink1。//獲得線元素的STNODEID值之后，直接可以得到點(diǎn)節(jié)點(diǎn)在數(shù)組中的位置=RoadNode[indexP2]。=RoadNode[indexP2].Neighbor。RoadNode[indexP2].Neighbor=vLink1。pFeatureL=()。}點(diǎn)的數(shù)組建立完成之后，可以開始遍歷線層元素，每取得一個(gè)線元素，則可以得到首尾節(jié)點(diǎn)的ID，根據(jù)首尾節(jié)點(diǎn)ID（即首尾節(jié)點(diǎn)在數(shù)組中的索引）得到首尾節(jié)點(diǎn)，分別為首尾節(jié)點(diǎn)建立鄰接關(guān)系vLink1和vLink2，從線元素獲得首尾節(jié)點(diǎn)的過程的時(shí)間復(fù)雜度為O（1），而外層while循環(huán)是遍歷線層元素，時(shí)間復(fù)雜度為O（n），經(jīng)過這一過程，拓?fù)潢P(guān)系基本建立完成，由于采用數(shù)組存儲VERTEX元素的目的是建立索引，減少建立拓?fù)潢P(guān)系時(shí)點(diǎn)的搜索時(shí)間，因此，拓?fù)潢P(guān)系建立完成后，為了方便運(yùn)算，也為了盡量減少數(shù)組元素所占用的大塊內(nèi)存區(qū)域，把VERTEX元素從數(shù)組中摘下并建立環(huán)狀鏈表：vWork=vHead。for(indexP=1。indexPNodeCount。indexP++){if(RoadNode[indexP]!=null){RoadNode[indexP].Prev=vWork。RoadNode[indexP].Next=。=RoadNode[indexP]。=RoadNode[indexP]。vWork=RoadNode[indexP]。}}=vHead。=vWork。通過這一步操作，環(huán)狀的鄰接多重表建立完成。以上三次遍歷并沒有嵌套關(guān)系，因此整個(gè)建立鄰接多重表的時(shí)間復(fù)雜度為O（n）。 查詢最短路徑查詢最短路徑：int flag=0。int c=0。vWork=。while(cPointCnt){//根據(jù)點(diǎn)節(jié)點(diǎn)的數(shù)量，循環(huán)設(shè)定點(diǎn)節(jié)點(diǎn)中各字段的初始值if(==pStartID){flag++。=vWork。}if(==pEndID){flag++。=vWork。}=0。=null。=。vWork=。c++。}由于鄰接多重表可以重復(fù)使用，因此在一次尋徑后，鏈表中的節(jié)點(diǎn)的一些屬性值可能被改變，因此需要重新初始化節(jié)點(diǎn)的屬性值，如查詢狀態(tài)Searched、最短路徑前導(dǎo)節(jié)點(diǎn)ShortPathPre，最短路徑值Weight等。sOpen=new SearchLink()。sClose=new SearchLink()。==null。=null。==null。=null。sTemp=new SearchLink()。=。=1。=0。=sTemp。==null。Insert(sTemp,ref sOpen)。//Insert函數(shù)按升序?qū)⒐?jié)點(diǎn)sTemp插入鏈表sOpen中while(!=nullamp。amp。!=2)//一旦鏈表sOpen變?yōu)榭?，或終點(diǎn)的最短路徑已經(jīng)找到，則查詢結(jié)束{sTemp=。vWork=。vLink=。=2。Delete(ref sTemp,ref sOpen)。//在sOpen鏈表中找到權(quán)值最小節(jié)點(diǎn)之后，將該節(jié)點(diǎn)從鏈表sOpen中移除，并插入鏈表sClose中，表示該節(jié)點(diǎn)的最短路徑已經(jīng)找到Insert(sTemp,ref sClose)。while(vLink!=null)//遍歷節(jié)點(diǎn)的各個(gè)鄰接點(diǎn){if(==0)//Searched字段表名該鄰接點(diǎn)的搜索狀態(tài)，如果是0，則表示該鄰接點(diǎn)從未被搜索過{=+。=。=1。=vWork。sTemp1=new SearchLink()。=。=sTemp1。InsertOrder(sTemp1,ref sOpen)。}else if(==1)//Searched如果為1，則表示該鄰接點(diǎn)已經(jīng)搜索過，但還沒有找到最短路徑{if(+)//如果權(quán)值不是最小，則需要重新計(jì)算權(quán)值{Delete(ref ,ref sOpen)。=+。=。=vWork。InsertOrder(,ref sOpen)。}}vLink=。}}在開始最短路徑查詢之前，首先定義兩個(gè)鏈表sOpen和sClose，sClose用來放置已經(jīng)找到最短路徑的節(jié)點(diǎn)，sOpen用來放置已經(jīng)搜索但還沒有找到最短路徑、等待繼續(xù)搜索的節(jié)點(diǎn)。其次需要初始化鄰接多重表，將每一個(gè)節(jié)點(diǎn)的Searched字段置為0，表明該節(jié)點(diǎn)還沒有被搜索過，并把節(jié)點(diǎn)權(quán)重置為無窮大（最大值）。這一過程為單循環(huán)，時(shí)間復(fù)雜度為O（n）。以上是最短路徑算法的主體部分，首先將源節(jié)點(diǎn)的Searched字段置為1，權(quán)重置為0，并插入鏈表sOpen中，而后進(jìn)入循環(huán)搜索最短路徑的過程。外循環(huán)用來遍歷鏈表sClose，直到鏈表sClose變?yōu)榭?，或者最短路徑的終點(diǎn)vTail的最短路徑被找到（Searched字段變?yōu)?）。而內(nèi)循環(huán)則遍歷sOpen中節(jié)點(diǎn)的鄰接關(guān)系，本算法實(shí)現(xiàn)過程中這一循環(huán)與節(jié)點(diǎn)數(shù)或線數(shù)并沒有數(shù)學(xué)關(guān)系，它的循環(huán)次數(shù)通常為2～5之間。在每次循環(huán)中，首先將節(jié)點(diǎn)置于鏈表sClose中，并把Searched值置為2，表明該節(jié)點(diǎn)已經(jīng)找到最短路徑，然后遍歷該節(jié)點(diǎn)的每一個(gè)鄰接點(diǎn)，首先判斷該鄰接點(diǎn)的搜索情況（Searched字段值），然后進(jìn)行插入或重新插入集合sOpen的操作（InsertOrder），程序中設(shè)置了兩個(gè)插入函數(shù)InsertOrder和Insert，InsertOrder函數(shù)專用來向sOpen中插入節(jié)點(diǎn)，這一過程需要進(jìn)行排序，因此隨著sOpen鏈表的規(guī)模增大，相應(yīng)的時(shí)間消耗也會增大，插入排序過程的時(shí)間復(fù)雜度為O（（n＋1）/2）。為了使計(jì)算最短路徑時(shí)搜索的節(jié)點(diǎn)范圍盡量縮小，程序中對每次更改Searched字段值之后的節(jié)點(diǎn)都要移出原集合（鏈表），這一方式使單次搜索最短路徑的效率得到很大的提高。但是隨之而來的問題是,單次搜索之后，原來的鄰接多重表被破壞了，在下一次搜索前不得不重新建立鄰接多重表，由于建立鄰接多重表時(shí)如果數(shù)據(jù)量比較大，則程序需要頻繁訪問外存儲器，造成了大量的時(shí)間開銷。而SearchLink類的引入，使得鄰接多重表可以“一次建立，多次使用”，真正提高算法的效率和實(shí)用性。SearchLink是純指針類，實(shí)例化的時(shí)候只占用很少的內(nèi)存開銷，因此這種以空間換時(shí)間的方法能夠有效的提高算法執(zhí)行的效率。第五章 GPS導(dǎo)航功能衛(wèi)星導(dǎo)航技術(shù)的飛速發(fā)展已逐漸取代了無線電導(dǎo)航、天文導(dǎo)航等傳統(tǒng)導(dǎo)航技術(shù)，而成為一種普遍采用的導(dǎo)航定位技術(shù)，并在精度、實(shí)時(shí)性、全天候等方面取得了長足進(jìn)步?，F(xiàn)不僅應(yīng)用于物理勘探、電離層測量和航天器導(dǎo)航等諸多民用領(lǐng)域，在軍事領(lǐng)域更是取得了廣泛的應(yīng)用——在彈道導(dǎo)彈、野戰(zhàn)指揮系統(tǒng)、精確彈道測量以及軍用地圖快速測繪等領(lǐng)域均大量采用了衛(wèi)星導(dǎo)航定位技術(shù)。有鑒于衛(wèi)星導(dǎo)航技術(shù)在民用和軍事領(lǐng)域的重要意義，使其得到了許多國家的關(guān)注。我國也于 2000年10月31日和12月21日成功發(fā)射了第一顆和第二顆導(dǎo)航定位試驗(yàn)衛(wèi)星并建立了我國第一代衛(wèi)星導(dǎo)航定位系統(tǒng)北斗導(dǎo)航系統(tǒng)，但由于起步晚也沒有得到廣泛應(yīng)用。目前在我國應(yīng)用最多的還是美國的GPS系統(tǒng)。GPS接收機(jī)可接收到準(zhǔn)確至納秒級的時(shí)間信息；用于預(yù)報(bào)未來幾個(gè)月內(nèi)衛(wèi)星所處概略位置的預(yù)報(bào)星歷；用于計(jì)算定位時(shí)所需衛(wèi)星坐標(biāo)的廣播星歷，精度為幾米至幾十米（各個(gè)衛(wèi)星不同，隨時(shí)變化）；以及GPS系統(tǒng)信息，如衛(wèi)星狀況等。GPS接收機(jī)對碼的量測就可得到衛(wèi)星到接收機(jī)的距離，由于含有接收機(jī)衛(wèi)星鐘的誤差及大氣傳播誤差，故稱為偽距。對0A碼測得的偽距稱為UA碼偽距，精度約為20米左右，對P碼測得的偽距稱為P碼偽距，精度約為2米左右。GPS接收機(jī)對收到的衛(wèi)星信號，進(jìn)行解碼或采用其它技術(shù)，將調(diào)制在載波上的信息去掉后，就可以恢復(fù)載波。嚴(yán)格而言，載波相位應(yīng)被稱為載波拍頻相位，它是收到的受多普勒頻移影響的衛(wèi)星信號載波相位與接收機(jī)本機(jī)振蕩產(chǎn)生信號相位之差。一般在接收機(jī)鐘確定的歷元時(shí)刻量測，保持對衛(wèi)星信號的跟蹤，就可記錄下相位的變化值，但開始觀測時(shí)的接收機(jī)和衛(wèi)星振蕩器的相位初值是不知道的，起始?xì)v元的相位整數(shù)也是不知道的，即整周模糊度，只能在數(shù)據(jù)處理中作為參數(shù)解算。相位觀測值的精度高至毫米，但前提是解出整周模糊度，因此只有在相對定位、并有一段連續(xù)觀測值時(shí)才能使用相位觀測值，而要達(dá)到優(yōu)于米級的定位精度也只能采用相位