最短路径之Dijkstra算法详细讲解(C)

1、最短路径之Dijkstra算法详细讲解1最短路径算法在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。（3）确定起点终点的最短路径问题：即已知起

2、点和终点，求两结点之间的最短路径。（4）全局最短路径问题：求图中所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。本文主要研究Dijkstra算法的单源算法。2Dijkstra算法Dijkstra算法Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

3、Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra算法思想Dijkstra算法思想为：设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶

4、点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。Dijkstra算法具体步骤（1）初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。（2）从U中选取一个距离v最小的顶点k,把k，加入S中（该选定的距离就是v到k的最短路径长度）。*汕-冲*汕-冲272&Dreefrwk.bloQ.1（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶

5、点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中。2.4Dijkstra算法举例说明如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）图一：Dijkstra无向图算法执行步骤如下表：1蜒u集合申kilA*-止商s=此时蚩过跖盘*TH臥E中间点-归QkCsD.蛊PA-JfezBA-C3他U中的顼点三itSTffiSSEaac=3Me为中向点，丛*峠这養昭辭径并V=*T1：Tm讣匕上面第一痢Hf町要短i此时剜旱

6、耿伍力首TCTIkfi*TCTE*TCT耳植IT中的顶.a.-co富規ATCT*岁収佰左银理$&XE,此Bi3=d（kEATCT昶1抚B曲中阿点，从ATtTS=$这条屋桓踌莊开舲扶i=*FC-T*=io比上厕缶:顋的4-C-D毛s#）址时劃D握值要改对占T#T中的頂点.=M求現ATCTD油報虫忠臺坦45S-AD此时狂aC、陰D览时厝極粘隹hF口HSATCTEATCTtt=E以话申同点，从ATCTD息案壘無貉蝕JFJSlt4也F*TCTD-E=S（HU：面解二tFBOATCTE刊捷快）*河至出勒H更改打ATHTE寸ATtTDTFK接EfiATcTE珂祝佰討垦短5选人E止血3=0C-爲D,Eim-

7、ftsitsa*寸冋atc=3，X-?CZ=5jK-C-E=7哄E为中闫鼠从ATCTE汕这条星迪拥屜开齬拽v=盘TtFETF叮誥比王面第四垮的-9痿曲时劉F取頂更蘆为点fCDTF=9发現ATCTDTF=9找悄为億瘫6?4Af-it|?ts=ah扎u,t,r百一*0,ATE,AT:TE=5*TCT1W那桑合己崔”査蹶骚最短路径之Dijkstra算法程序(C#)usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.

8、Text;usingSystem.Windows.Forms;namespacedjpublicpartialclassForm1:FormFindSortPathfsp=newFindSortPath();/最短路径对象intCombox1Select=0;intCombox2Select=0;publicForm1()InitializeComponent();privatevoidForm1_Load(objectsender,EventArgse)comboBox1.Items.Add(A);comboBox1.Items.Add(B);comboBox1.Items.Add(C);c

9、omboBox1.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);privatevoidcomboBox1_SelectedIndexChanged(objectsender,EventArgse)Combox1Select=1;privatevoidc

10、omboBox2_SelectedIndexChanged(objectsender,EventArgse)Combox2Select=1;privatevoidbutton1_Click(objectsender,EventArgse)intm=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;intglength=(int)Math.Sqrt(G.Length);/算出顶点数Combox2Selectintmaxsize=1000;/当权值超过1000时说明没有路径Combo

11、x2Selectif(Combox1Select=1&1&comboBox1.SelectedIndex!=comboBox2.SelectedIndex)fsp.vo=comboBox1.SelectedIndex;/源点fsp.vi=comboBox2.SelectedIndex;/终点fsp.OneToOneSP(G,glength,maxsize);stringstr=;inttemp=newintfsp.ShortPath.Length;for(inti=0;ifsp.ShortPath.Length;i+)str=str+comboBox1.Itemsfsp.ShortPathi.ToString()+textBox1.Text=str;textBox2.Text=fsp.ShortDist.ToString();elseMessageBox.Show(请选择起点和终点”)；privatevoidbutton2_Click(objectsender,EventArgse)textBox1.Text=;textBo