高中信息競賽數(shù)據(jù)結構—最短路徑-展示頁
2025-05-22 10:40本頁面
【正文】 路徑問題。一般來講，目前還未發(fā)現(xiàn)比最好的單源算法更快的方法。 ? ： 對于某給定頂點 u和 v，找出從 u到 v的一條最短路徑。最短路徑 最短路問題的類型 ? ： 找出從每一頂點 v到某指定頂點 u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問題轉化為單源最短路徑問題。如果我們解決了源頂點為 u的單源問題，則這一問題也就獲得了解決。 ? ：對于每對頂點 u和 v，找出從 u到 v的最短路徑。該算法在圖的傳遞閉包的基礎上形成； ? Dijkstra算法： 在邊權非負的有向圖中計算單源最短路徑問題。所謂一般情況，指的是有向圖的邊權可以為負 ,但不允許存在負權回路。 計算單源最短路問題（ Dijkstra算法） ?計算單源最短路的思維方向： 每次延長最短路時選擇權最小的邊，并調整最短路外每個結點至出發(fā)結點的路長 ?計算單源最短路的步驟： 把圖中所有結點分為兩組，每一個結點對應一個距離值： 第一組：包括已確定最短路徑的結點，結點對應的距離值是由 v0到此結點的最短路徑長度； 第二組：包括尚未確定最短路徑的結點，結點對應的距離值 是 v0經由第一組結點（中間結點）至此結點的最短路徑長度； 我們按最短路徑長度遞增的順序把第二組的結點加到第一組中去，直至v0可達的所有結點都包含于第一組。 ???????EvvEvvwdi s tiiii ),(),(000? 初始時 v0進入第一組， v0的距離值為 0；第二組包含其它所有結點，這些結點對應的距離值為 v0到它的值即 map[v0][vi] ?然后每次從第二組的結點中選一個其距離值為最小的結點 vm加到第一組中。修改后再選距離值最小的一個結點加入到第一組中， … 。顯然，這種從第二組的結點中選距離值最小的結點擴展是一種貪心策略。 int map[][]。 //存儲到源點的最短路徑長度 int path[]。 //標記該頂點是否已經計算 ①從文件中讀入圖的鄰接矩陣 g； for(i=1。i++) for(j=1。j++) cinmap[i][j]。i=n。j=n。 //把沒有通路的點 (map[i][j]==0)間的路徑置為最大值 cinv。 for(i=1。i++)//初始化 ,置初值 {dist[i]=map[v][i]。vs[i]=false。//處理源點 path[v]=0。//標記訪問 for(i=1。i++)//Dijkstra算法核心 { w=maxint。j=n。amp。w=dist[j]。//將最短點做標記 for(j=1。j++)//利用找到的點優(yōu)化還沒有訪問的點 if(!vs[j]amp。(map[k][j]!=maxint)amp。dist[k]+map[k][j]dist[j]) {dist[j]:=dist[k]+map[k,j]。 //保存路徑 } } } ④ 輸出； 典型例題 — 最短路徑問題 1249 Description: 平面上有 n個點（ n＜＝ 100），每個點的坐標均在 10000到 10000之間．其中的一些點之間有連線．若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離．現(xiàn)在的任務是找出從一點到另一點之間的最短路徑． Input： 共 n+m+3行 第一行為整數(shù) n． 第２行到第 n＋行，每行兩個整數(shù) x和 y，描述了一個點的坐標（以一個空格分開） 第 n＋２行為一個整數(shù) m，表示圖中連線的個數(shù)． 以后的 m行，每行描述一條連線，由兩個整數(shù) i和 j組成，表示第 i個點和第 j個點之間有連線． 最后一行；兩個整數(shù) s和 t，分別表示源點和目標點． Output: 僅一行，一個實數(shù)（保留兩位小數(shù)），表示從 s到 t的最短路徑長度 典型例題 — 最短路徑問題 1249 Sample Input 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 Sample Output: 典型例題 — 最短路徑問題 1249 int main() { int i,j,m,num1,num2。 for(i=1。i++) for(j=1。j++)map[i][j]=maxint。i=n。x[i],amp。 cinm。i=m。num1,amp。 map[num1][num2]=map[num2][num1]=dist(num1,num2)。 dijkstra(st)。 } 典型例題 — 最短路徑問題 1249 void dijkstra(int v) { double min。 for(i=1。i++) {dis[i]=map[v][i]。} dis[st]=0。 for(i=1。i++) { min=maxint。j=n。amp。min=dis[j]。 for(j=1。j++)
法律信息相關推薦
鄂ICP備17016276號-1