Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法用于计算一个节点到其他所有节点的最短路径主要特点是以起始点为中心向外层层扩展直到扩展到终点为止
Dijkstra一般的表述通常有两种方式一种用永久和临时标号方式一种是用OPEN CLOSE表方式
用OPENCLOSE表的方式其采用的是贪心法的算法策略大概过程如下
声明两个集合open和closeopen用于存储未遍历的节点close用来存储已遍历的节点
初始阶段将初始节点放入close其他所有节点放入open
以初始节点为中心向外一层层遍历获取离指定节点最近的子节点放入close并从新计算路径直至close包含所有子节点
代码实例如下
Node对象用于封装节点信息包括名字和子节点
[java]
public class Node {
private String name;
private Map<NodeInteger> child=new HashMap<NodeInteger>（）
public Node（String name）{
thisname=name;
}
public String getName（） {
return name;
}
public void setName（String name） {
thisname = name;
}
public Map<Node Integer> getChild（） {
return child;
}
public void setChild（Map<Node Integer> child） {
thischild = child;
}
}
MapBuilder用于初始化数据源返回图的起始节点
[java]
public class MapBuilder {
public Node build（Set<Node> open Set<Node> close）{
Node nodeA=new Node（A）
Node nodeB=new Node（B）
Node nodeC=new Node（C）
Node nodeD=new Node（D）
Node nodeE=new Node（E）
Node nodeF=new Node（F）
Node nodeG=new Node（G）
Node nodeH=new Node（H）
nodeAgetChild（）put（nodeB ）
nodeAgetChild（）put（nodeC ）
nodeAgetChild（）put（nodeD ）
nodeAgetChild（）put（nodeG ）
nodeAgetChild（）put（nodeF ）
nodeBgetChild（）put（nodeA ）
nodeBgetChild（）put（nodeF ）
nodeBgetChild（）put（nodeH ）
nodeCgetChild（）put（nodeA ）
nodeCgetChild（）put（nodeG ）
nodeDgetChild（）put（nodeA ）
nodeDgetChild（）put（nodeE ）
nodeEgetChild（）put（nodeD ）
nodeEgetChild（）put（nodeF ）
nodeFgetChild（）put（nodeE ）
nodeFgetChild（）put（nodeB ）
nodeFgetChild（）put（nodeA ）
nodeGgetChild（）put（nodeC ）
nodeGgetChild（）put（nodeA ）
nodeGgetChild（）put（nodeH ）
nodeHgetChild（）put（nodeB ）
nodeHgetChild（）put（nodeG ）
openadd（nodeB）
openadd（nodeC）
openadd（nodeD）
openadd（nodeE）
openadd（nodeF）
openadd（nodeG）
openadd（nodeH）
closeadd（nodeA）
return nodeA;
}
}
图的结构如下图所示
Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java]
public class Dijkstra {
Set<Node> open=new HashSet<Node>（）
Set<Node> close=new HashSet<Node>（）
Map<StringInteger> path=new HashMap<StringInteger>（）//封装路径距离
Map<StringString> pathInfo=new HashMap<StringString>（）//封装路径信息
public Node init（）{
//初始路径因没有A>E这条路径所以path（E）设置为IntegerMAX_VALUE
pathput（B ）
pathInfoput（B A>B）
pathput（C ）
pathInfoput（C A>C）
pathput（D ）
pathInfoput（D A>D）
pathput（E IntegerMAX_VALUE）
pathInfoput（E A）
pathput（F ）
pathInfoput（F A>F）
pathput（G ）
pathInfoput（G A>G）
pathput（H IntegerMAX_VALUE）
pathInfoput（H A）
//将初始节点放入close其他节点放入open
Node start=new MapBuilder（）build（openclose）
return start;
}
public void computePath（Node start）{
Node nearest=getShortestPath（start）//取距离start节点最近的子节点放入close
if（nearest==null）{
return;
}
closeadd（nearest）
openremove（nearest）
Map<NodeInteger> childs=nearestgetChild（）
for（Node child:childskeySet（））{
if（ntains（child））{//如果子节点在open中
Integer newCompute=pathget（nearestgetName（））+childsget（child）
if（pathget（childgetName（））>newCompute）{//之前设置的距离大于新计算出来的距离
pathput（childgetName（） newCompute）
pathInfoput（childgetName（） pathInfoget（nearestgetName（））+>+childgetName（））
}
}
}
computePath（start）//重复执行自己确保所有子节点被遍历
computePath（nearest）//向外一层层递归直至所有顶点被遍历
}
public void printPathInfo（）{
Set<MapEntry<String String》 pathInfos=pathInfoentrySet（）
for（MapEntry<String String> pathInfo:pathInfos）{
Systemoutprintln（pathInfogetKey（）+:+pathInfogetValue（））
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath（Node node）{
Node res=null;
int minDis=IntegerMAX_VALUE;
Map<NodeInteger> childs=nodegetChild（）
for（Node child:childskeySet（））{
if（ntains（child））{
int distance=childsget（child）
if（distance<minDis）{
minDis=distance;
res=child;
}
}
}
return res;
}
}
Main用于测试Dijkstra对象
[java]
public class Main {
public static void main（String[] args） {
Dijkstra test=new Dijkstra（）
Node start=testinit（）
putePath（start）
testprintPathInfo（）
}
}
打印输出如下
D:A>D
E:A>F>E
F:A>F
G:A>C>G
B:A>B
C:A>C
H:A>B>H
