《最短路径算法——dijkstra.docx》由会员分享，可在线阅读，更多相关《最短路径算法——dijkstra.docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最短路径算法dijkstra前提在一张图里不能有权值为负数的边。给你一个出发点求出发点到所有结点的最短间隔是多少假如无法到达某个点那么到这个点的间隔是正无穷一般出如今有向图里面。举个例子看如下列图右边集合表示的是A点到集合中各个点的最短间隔。一开场假设A点到所有其它点的间隔是正无穷就是假设都不可到达A作为一个桥连点出现后A到B点的间隔就是原先A到A0的间隔加上A到B的间隔1后面的类似所以得到如下列图当A这个点的记录使用完了之后就永远不去改动它就是上图中圈起来的A点。然后在剩下的记录中选一个最小的记录B点对应1意思就是从原点出发到达B的间隔是1再以B作为桥连点往外找。发现B到C的间隔为2B到E的
2、间隔为170所以可以更新表中C点的记录为3ABBCE的记录更新为171ABBE。之后B点这条记录也永远不去改动。在表中使用了哪条记录就将其锁住再也不碰它。接下来就是C点。同样的逻辑玩下去。最终表里全部锁死的记录就是dijkstra要求的记录。注意中间假如碰到间隔一样的可以不更新。这好似有点贪心思想啊。但问题是怎样在表里找最小的记录呢可以每次遍历来找但是有点费事。所以更好的方式是利用小根堆。小根堆会自动组织好每次把最小的值弹出来但在这里我们还有一个要求就是我们有可能要更改已经在堆里组织好的值这样的话系统提供的堆实现不了。我们需要手动改写堆推荐看看这两篇文章。可以更好理解dijkstra算法的改良
3、。然后我们依次来看自己手写的小根堆要实现的功能有哪些1add()添加一条记录的方法就是从原点到某个点的间隔是多少并且按间隔来组织2update()更新的方法需要更新某条记录的间隔。比方原点到X点的间隔是100但是通过某个桥连点到X的间隔是20了所以这条记录的间隔就要更新成20并且这条记录要在小根堆里往上heapInsert()自动组织好顺序3ignore()忽略点某个已经使用过的结点的方法。小根堆里装的东西的构造就是publicstaticclassNodeRecordpublicNodenode;publicintdistance;publicNodeRecord(Nodenode,intd
4、istance)this.nodenode;this.distancedistance;以下代码分别实现了dijkstra算法的两种方法packagecom.harrison.class11;importjava.util.HashMap;importjava.util.HashSet;importjava.util.Map.Entry;importcom.harrison.class11.Code01_NodeEdgeGraph.*;publicclassCode07_dijkstra/从from点到key的最短间隔是valuepublicstaticHashMapNode,Integerd
5、ijkstra1(Nodefrom)HashMapNode,IntegerdistanceMapnewHashMap();distanceMap.put(from,0);/一开场自己到自己的间隔当然是0/锁住已经使用过的记录HashSetNodeselectedNodesnewHashSet();NodeminNodegetMinDistanceNodeAndUnselectedNode(distanceMap,selectedNodes);while(minNode!null)intdistancedistanceMap.get(minNode);for(Edgeedge:minNode.e
6、dges)NodetoNodeedge.to;if(!distanceMap.containsKey(toNode)distanceMap.put(toNode,distanceedge.weight);elsedistanceMap.put(edge.to,Math.min(distanceMap.get(toNode),distanceedge.weight);selectedNodes.add(minNode);minNodegetMinDistanceNodeAndUnselectedNode(distanceMap,selectedNodes);returndistanceMap;/
7、在distanceMap表里面排除掉在selectedNodes集合的点然后选那么间隔最小的点返回publicstaticNodegetMinDistanceNodeAndUnselectedNode(HashMapNode,IntegerdistanceMap,HashSetNodeselectedNodes)NodeminNodenull;intminDistanceInteger.MAX_VALUE;/EntrySet可以遍历HashMap中的值for(EntryNode,Integerentry:distanceMap.entrySet()Nodenodeentry.getKey();
8、intdistanceentry.getValue();if(!selectedNodes.contains(node)distanceminDistance)minNodenode;minDistancedistance;returnminNode;publicstaticclassNodeRecordpublicNodenode;publicintdistance;publicNodeRecord(Noden,intd)noden;distanced;publicstaticclassNodeHeap/实际的堆构造privateNodenodes;/key在堆中的位置就是value/假如v
9、alue是-1代表这个结点曾经进过堆进来之后弹出了privateHashMapNode,IntegerheapIndexMap;/源结点到key的最小间隔就是valueprivateHashMapNode,IntegerdistanceMap;privateintsize;/堆上有多少个点publicNodeHeap(intsize)nodesnewNodesize;heapIndexMapnewHashMap();distanceMapnewHashMap();this.size0;publicbooleanisEmpty()returnsize0;/假如某个结点在heapIndexMap表
10、有记录表示曾经进过堆publicBooleanisEntered(Nodenode)returnheapIndexMap.containsKey(node);publicbooleaninHeap(Nodenode)returnisEntered(node)heapIndexMap.get(node)!-1;publicvoidheapInsert(Nodenode,intindex)while(distanceMap.get(nodesindex)distanceMap.get(nodes(index-1)/2)swap(index,(index-1)/2);index(index-1)/2
11、;publicvoidheapfiy(intindex,intsize)intleft2*index1;while(leftsize)intsmallest(left1size)(distanceMap.get(nodesleft1)distanceMap.get(nodesleft)?left1:left;smallestdistanceMap.get(nodessmallest)distanceMap.get(nodesindex)?smallest:index;if(smallestindex)break;swap(smallest,index);indexsmallest;left2*
12、index1;privatevoidswap(intindex1,intindex2)heapIndexMap.put(nodesindex1,index2);heapIndexMap.put(nodesindex2,index1);Nodetmpnodesindex1;nodesindex1nodesindex2;nodesindex2tmp;/有一个点node假如发现了一个从源节点到node的间隔为distance/判断要不要更新假如需要更新就更新publicvoidaddOrUpdateOrIgnore(Nodenode,intdistance)if(inHeap(node)/假如结点在
13、堆上有可能更新完记录后间隔变小所以需要调整堆distanceMap.put(node,Math.min(distanceMap.get(node),distance);heapInsert(node,heapIndexMap.get(node);if(!isEntered(node)/假如没有进过堆那么将这个结点挂在堆的最后一个结点nodessizenode;/这个结点的位置就在heapIndexMap表的size位置上heapIndexMap.put(node,size);distanceMap.put(node,distance);heapInsert(node,size);/假如两个if
14、都没中讲明这个结点既不在堆上但是又进来过/相当于什么都没做就直接返回publicNodeRecordpop()NodeRecordnodeRecordnewNodeRecord(nodes0,distanceMap.get(nodes0);swap(0,size-1);/堆顶弹出后标记为-1并移除相应的间隔记录heapIndexMap.put(nodessize-1,-1);distanceMap.remove(nodessize-1);/释放size-1位置上的东西nodessize-1null;heapfiy(0,-size);returnnodeRecord;/改良后的dijkstra算
15、法/从head出发所有head能到达的结点/生成到达每个结点的最小途径记录并返回publicstaticHashMapNode,Integerdijkstra2(Nodehead,intsize)NodeHeapnodeHeapnewNodeHeap(size);nodeHeap.addOrUpdateOrIgnore(head,0);HashMapNode,IntegeransnewHashMap();while(!nodeHeap.isEmpty()NodeRecordrecorednodeHeap.pop();Nodecurrecored.node;intdistancerecored.distance;for(Edgeedge:cur.edges)nodeHeap.addOrUpdateOrIgnore(edge.to,edge.weightdistance);ans.put(cur,distance);returnans;