最短路径算法——Dijkstra算法

最短路径算法——Dijkstra算法

Dijkstra算法在刚开始在学数据结构的时候，完全没弄明白，主要是也不怎么想去弄明白。而从学校出来到现在，最短路径算法都没有实际运用过，最近在一个GIS项目中总算用到了，于是乎把教材重温了下，同时查阅了网上一些资料，借鉴了一些别人的东西，并顺利用写进了项目中，文中的主要代码来自于园子里的一位大哥，这位大哥对通用框架的研究很深入，他的链接为：http://zhuweisky.cnblogs.com/archive/2005/09/29/246677.html（最短路径）。另外，文章的最后面的一些链接是我找资料的时候用到过的，有兴趣

的朋友可以去看看。

最短路径分析在事故抢修、交通指挥、GPS导航等行业应用中使用的非常广泛， 以至于大多数GIS平台都会把这个分析功能作为一个最基础的功能集成进去，如ARCGIS，SuperMap等。个人感觉想要了解这个算法的来龙去脉，一方面是参与相关书籍仔细理解，另外一个最重要的是要去调试代码。由于历史原因，对于书上的伪C代码，我是完全不感兴趣的，而且由于有严格的数学证明，所以看起来相对较难，而对于面向对象实现的算法，我很感兴趣，也感觉很容易理解，所以一边针对C#实现的面向对象代码再一边对照书籍，感觉理解的层次就加深了。

Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法，要求理解Dijstra的算法，同时还要理解图的一些基本概念，图由节点和边构成，将节点和边看成对象，每个对象有自己的特有属性，如在GIS中，一个节点必须都有ID，横坐标，纵坐标等基本属性，边有起点节点，终点节点，长度等属性，而最短路径分析，就是根据边的长度（权值）进行分析的。

边的定义如下：

publicclassEdge
{
publicstringStartNodeID;
publicstringEndNodeID;
publicdoubleWeight;//权值，代价
}

节点的定义：

publicclassNode
{
privatestringiD;
privateList<Edge>edgeList;//Edge的集合－－出边表

publicNode(stringid)
{
this.iD=id;
this.edgeList=newList<Edge>();
}

#regionproperty

publicstringID
{
get
{
returnthis.iD;
}
}

publicList<Edge>EdgeList
{
get
{
returnthis.edgeList;
}
}
#endregion
}

本次用于分析的拓扑图如下：(A为起点，D为终点，边上的数字为权值)

　　

利用上述的边与节点的定义，可以通过代码简单的构成如下图：

publicclassGraph
{
publicList<Node>m_nodeList=null;
publicGraph()
{
m_nodeList=newList<Node>();
}

///<summary>
///获取图的节点集合
///</summary>
publicList<Node>NodeList
{
get{returnthis.m_nodeList;}
}

///<summary>
///初始化拓扑图
///</summary>
publicvoidInit()
{
//*****************BNode*******************
NodeaNode=newNode("A");
m_nodeList.Add(aNode);
//A->B
EdgeaEdge1=newEdge();
aEdge1.StartNodeID=aNode.ID;
aEdge1.EndNodeID="B";
aEdge1.Weight=10;
aNode.EdgeList.Add(aEdge1);
//A->C
EdgeaEdge2=newEdge();
aEdge2.StartNodeID=aNode.ID;
aEdge2.EndNodeID="C";
aEdge2.Weight=20;
aNode.EdgeList.Add(aEdge2);
//A->E
EdgeaEdge3=newEdge();
aEdge3.StartNodeID=aNode.ID;
aEdge3.EndNodeID="E";
aEdge3.Weight=30;
aNode.EdgeList.Add(aEdge3);

//*****************BNode*******************
NodebNode=newNode("B");
m_nodeList.Add(bNode);
//B->C
EdgebEdge1=newEdge();
bEdge1.StartNodeID=bNode.ID;
bEdge1.EndNodeID="C";
bEdge1.Weight=5;
bNode.EdgeList.Add(bEdge1);
//B->E
EdgebEdge2=newEdge();
bEdge2.StartNodeID=bNode.ID;
bEdge2.EndNodeID="E";
bEdge2.Weight=10;
bNode.EdgeList.Add(bEdge2);

//*****************CNode*******************
NodecNode=newNode("C");
m_nodeList.Add(cNode);
//C->D
EdgecEdge1=newEdge();
cEdge1.StartNodeID=cNode.ID;
cEdge1.EndNodeID="D";
cEdge1.Weight=30;
cNode.EdgeList.Add(cEdge1);

//*****************DNode*******************
NodedNode=newNode("D");
m_nodeList.Add(dNode);

//*****************ENode*******************
NodeeNode=newNode("E");
m_nodeList.Add(eNode);
//E->D
EdgeeEdge1=newEdge();
eEdge1.StartNodeID=eNode.ID;
eEdge1.EndNodeID="D";
eEdge1.Weight=20;
eNode.EdgeList.Add(eEdge1);
}
}

有了拓扑节点和边，就可以根据算法构造其他最短路径分析的对象了，主要步骤如下：

Ø初始化图中的从A出发的路径集合：

///<summary>
///PlanCourse缓存从源节点到其它任一节点的最小权值路径（路径表）
///</summary>
publicclassPlanCourse
{
privateHashtablehtPassedPath;

#regionctor
publicPlanCourse(List<Node>nodeList,stringoriginID)
{
this.htPassedPath=newHashtable();

NodeoriginNode=null;
foreach(NodenodeinnodeList)
{
if(node.ID==originID)
{
originNode=node;
}
else
{
PassedPathpPath=newPassedPath(node.ID);
this.htPassedPath.Add(node.ID,pPath);
}
}

if(originNode==null)
{
thrownewException("Theoriginnodeisnotexist!");
}

this.InitializeWeight(originNode);
}

///<summary>
///通过指定节点的边的权值初始化路径表
///</summary>
///<paramname="originNode"></param>
privatevoidInitializeWeight(NodeoriginNode)
{
if((originNode.EdgeList==null)||(originNode.EdgeList.Count==0))
{
return;
}

foreach(EdgeedgeinoriginNode.EdgeList)
{
PassedPathpPath=this[edge.EndNodeID];
if(pPath==null)
{
continue;
}

pPath.PassedIDList.Add(originNode.ID);
pPath.Weight=edge.Weight;
}
}
#endregion

///<summary>
///获取指定点的路径表
///</summary>
///<paramname="nodeID"></param>
///<returns></returns>
publicPassedPaththis[stringnodeID]
{
get
{
return(PassedPath)this.htPassedPath[nodeID];
}
}
}

Ø从A中最短路径集合中找到一个最短的路径点Vi开始分析

///<summary>
///从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点
///</summary>
///<returns></returns>
privateNodeGetMinWeightRudeNode(PlanCourseplanCourse,List<Node>nodeList,stringoriginID)
{
doubleweight=double.MaxValue;
NodedestNode=null;

foreach(NodenodeinnodeList)
{
if(node.ID==originID)
{
continue;
}

PassedPathpPath=planCourse[node.ID];
if(pPath.BeProcessed)
{
continue;
}

if(pPath.Weight<weight)
{
weight=pPath.Weight;
destNode=node;
}
}

returndestNode;
}

Ø修正从A出发至Vi最短路径，并重新选择另一个最短路径点Vj点开始分析，重新执行上述步骤的路径分析

while(curNode!=null)
{
PassedPathcurPath=planCourse[curNode.ID];
foreach(EdgeedgeincurNode.EdgeList)
{
PassedPathtargetPath=planCourse[edge.EndNodeID];
doubletempWeight=curPath.Weight+edge.Weight;

if(tempWeight<targetPath.Weight)
{
targetPath.Weight=tempWeight;
targetPath.PassedIDList.Clear();

for(inti=0;i<curPath.PassedIDList.Count;i++)
{
targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());
}

targetPath.PassedIDList.Add(curNode.ID);
}
}

//标志为已处理
planCourse[curNode.ID].BeProcessed=true;
//获取下一个未处理节点
curNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);
}

Ø重复上述两个步骤，一直到所有的对象都分析完为止。

Ø这个时候的路径集合表中已经保存了从A到任意一点的最短路径集合了。

///<summary>
///从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果
///</summary>
///<returns></returns>
privateRoutePlanResultGetResult(PlanCourseplanCourse,stringdestID)
{
PassedPathpPath=planCourse[destID];

if(pPath.Weight==int.MaxValue)
{
RoutePlanResultresult1=newRoutePlanResult(null,int.MaxValue);
returnresult1;
}

string[]passedNodeIDs=newstring[pPath.PassedIDList.Count];
for(inti=0;i<passedNodeIDs.Length;i++)
{
passedNodeIDs[i]=pPath.PassedIDList[i].ToString();
}

RoutePlanResultresult=newRoutePlanResult(passedNodeIDs,pPath.Weight);

returnresult;
}

最短路径的结果类定义如下：

publicclassRoutePlanResult
{
publicRoutePlanResult(string[]passedNodes,doublevalue)
{
m_resultNodes=passedNodes;
m_value=value;
}

privatestring[]m_resultNodes;
///<summary>
///最短路径经过的节点
///</summary>
publicstring[]ResultNodes
{
get{returnm_resultNodes;}
}

privatedoublem_value;
///<summary>
///最短路径的值
///</summary>
privatedoubleValue
{
get{returnm_value;}
}
}