最短路徑之Dijkstra算法詳細講解C#

1、最短路徑之Dijkstra算法詳細講解1最短路徑算法在日常生活中，我們?nèi)绻枰３Ｍ礎(chǔ)地區(qū)和B地區(qū)之間，我們最希望知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中，那一條路徑的路途最短。最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖(由結(jié)點和路徑組成的)中兩結(jié)點之間的最短路徑。算法具體的形式包括：(1)確定起點的最短路徑問題：即起始結(jié)點，求最短路徑的問題。(2)確定終點的最短路徑問題：與確定起點的問題相反，該問題是終結(jié)結(jié)點，求最短路徑的 問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)確實 定起點的問題。(3)確定起點終點的最短路徑問題：即起點和終點

2、，求兩結(jié)點之間的最短路徑。(4)全局最短路徑問題：求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱做最短路徑算法，有時被簡稱作路徑算法最常用的路徑算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。本文主要研究Dijkstra算法的單源算法。2Dijkstra算法2.1Dijkstra算法Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以 起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。Dijks

3、tra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為根本內(nèi)容有詳細的介紹，如數(shù)據(jù) 結(jié)構(gòu)，圖論，運籌學(xué)等等。2.2Dijkstra算法思想Dijkstra算法思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合(用S表示，初始時S中只有一個源點，以后每求得一條最短路徑，就將參加到集合S中，直到全部頂點都參加到S中，算法就結(jié)束了)，第二組為其余未確定最短路徑的頂點集合(用U表示)，按最短路徑長度的遞增次序依次把第二組的頂點參加S中。在參加的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點

4、對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。2.3Dijkstra算法具體步驟(1)初始時，S只包含源點，即S = ,v的距離為0。U包含除v外的其他頂點，U中頂點u距離為 邊上的權(quán)(假設(shè)v與u有邊)或)(假設(shè)u不是v的出邊鄰接點)。(2)從U中選取一個距離v最小的頂點k,把k,參加S中(該選定的距離就是v到k的最短路徑 長度)。3以k為新考慮的中間點，修改U中各頂點的距離；假設(shè)從源點v到頂點u u U的距離經(jīng)過 頂點k比原來距離不經(jīng)過頂點k短，那么修改頂點u的距離值，修改后的距離值的頂點k的距離加

5、上邊 上的權(quán)。4重復(fù)步驟2和3直到所有頂點都包含在S中。2.4 Dijkstra算法舉例說明如下列圖，設(shè)A為源點，求A到其他各頂點B、C、D、E、F的最短路徑。線上所標注為相鄰線段 之間的距離，即權(quán)值。注：此圖為隨意所畫，其相鄰頂點間的距離與圖中的目視長度不能一一對等圖一：Dijkstra無向圖算法執(zhí)行步驟如下表:M一 - _-集g中l(wèi)iU為中poixs. P A A開益說(=至C. B, E. TA -)=6*-C=3uTKIftU叩的翌點三aa第JUTC=3根值汨|雄1 2遑 Ems=c成t為中i虬苴，隊*7匚=3這茶曜規(guī)SS徑開UH0 低虬F* TC T A51比上第環(huán)一綁由 f 玷妥暗

6、*TZTP=6ATCTlzTA TC f苒熠U中的用*t害WUTOT恥9峽伯為豪溟3速入 J如Cx 此的總窸駱徑RTA# , A-C=3 * *-C-=5為申詞點，從Jk-K T45最蓋最燧 路徑升惦投咋&E- TATCTET到0比上而jft二爆的ATCT6整蚯， 散時割。枳僮夏權(quán)為虹T IXA TCT* 一苴觸U中的添點=OQESUTCTg鞍值為瑕祖1 - - - - -4透心邱0 I 卜DA TEFATC4,KTCTA5 ATCTW以D為中間鼠從A TC TD遮事姓購饒 開蛤技岫工F-*l TE =e1=5* |TTXATtTE =7以丹中間點.從A TC TE =7誼條最塔鳩性棄

7、柚拉 ATCTETF ：I2(彳霍to WSIFOUEX為ATCTPTF 0SOftATCTItTF$或傅為1ft息遺入F. it!S= C-B=5 TCTBSATCTE =? , A-4C TP TF /U案合己堂，香摳完畢.如m n rw k$ 3 Bn最短路徑之 Dijkstra算法程序(C#)using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windo

8、ws.Forms;namespace djpublic partial class Form1 : FormFindSortPath fsp = new FindSortPath(); /最短路徑對象int Combox1Select = 0;int Combox2Select = 0;public Form1()InitializeComponent();private void Form1_Load(object sender, EventArgs e)comboBox1.Items.Add(A);comboBox1.Items.Add(B);comboBox1.Items.Add(C);

9、comboBox1.Items.Add(D);comboBox1.Items.Add(E);comboBox1.Items.Add(F);comboBox2.Items.Add(A);comboBox2.Items.Add(B);comboBox2.Items.Add(C);comboBox2.Items.Add(D);comboBox2.Items.Add(E);comboBox2.Items.Add(F);private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)Combox1Select =1;priva

10、te void comboBox2_SelectedIndexChanged(object sender, EventArgs e) Combox2Select = 1;)private void button1_Click(object sender, EventArgs e)(int m = 2000;int, G =(m,6,3,m,m,m,6,m,2,5,m,m,3,2,m,3,4,m,m,5,3,m,2,3,m,m,4,2,m,5,m,m,m,3,5,m;int glength = (int)Math.Sqrt(G.Length);/算出頂點數(shù)int maxsize = 1000;/

11、當(dāng)權(quán)值超過1000時說明沒有路徑if (Combox1Select=1& Combox2Select1&comboBox1.SelectedIndex !=comboBox2.SelectedIndex)fsp.vo = comboBox1.SelectedIndex;/源點fsp.vi = comboBox2.SelectedIndex;終點fsp.OneToOneSP(G , glength, maxsize);string str = ;int temp = new intfsp.ShortPath.Length;for (int i = 0; i fsp.ShortPath.Length; i+)str=str + comboBox1.Itemsfsp.ShortPathi.ToString()+;textBox1.Text = str;textBox2.Text = fsp.ShortDist.ToString();elseMessageBox.Show(請選擇起點和終點)；private void button2_Click(object sender, EventArgs e)textBox1.Text =;textBox2.Text =;private