图--06---加权有向图、最短路径、Dijstra算法

文章目录加权有向图加权有向图---边的表示1. API设计2. 代码加权有向图----图的实现1. API设计2. 代码最短路径定义在一副加权有向图中从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。性质最短路径树最短路径树API设计松弛技术边的松弛顶点的松弛Dijstra算法实现辅助类1. DirectedEdge----加权有向边2. EdgeWeightedDigraph----加权有向图3. IndexMinPriorityQueue----最小优先队列Dijstra算法代码测试查找最短路径,0-6的最短路径加权有向图之前学习的加权无向图中边是没有方向的并且同一条边会同时出现在该边的两个顶点的邻接表中为了能够处理含有方向性的图的问题我们需要实现以下加权有向图。加权有向图—边的表示1. API设计2. 代码publicclassDirectedEdge{privatefinalintv;//起点privatefinalintw;//终点privatefinaldoubleweight;//当前边的权重//通过顶点v和w以及权重weight值构造一个边对象publicDirectedEdge(intv,intw,doubleweight){this.vv;this.ww;this.weightweight;}//获取边的权重值publicdoubleweight(){returnweight;}//获取有向边的起点publicintfrom(){returnv;}//获取有向边的终点publicintto(){returnw;}}加权有向图----图的实现1. API设计2. 代码packagegraph.tu;importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedDeque;importjava.util.concurrent.ConcurrentLinkedQueue;publicclassEdgeWeightedDigraph{//顶点总数privatefinalintV;//边的总数privateintE;//邻接表privateQueueDirectedEdge[]adj;//创建一个含有V个顶点的空加权有向图publicEdgeWeightedDigraph(intV){//初始化顶点数量this.VV;//初始化边的数量this.E0;//初始化邻接表this.adjnewQueue[V];for(inti0;iadj.length;i){adj[i]newConcurrentLinkedDequeDirectedEdge();}}//获取图中顶点的数量publicintV(){returnV;}//获取图中边的数量publicintE(){returnE;}//向加权有向图中添加一条边epublicvoidaddEdge(DirectedEdgee){//边e是有方向的所以只需要让e出现在起点的邻接表中即可intve.from();adj[v].offer(e);E;}//获取由顶点v指出的所有的边publicQueueDirectedEdgeadj(intv){returnadj[v];}//获取加权有向图的所有边publicQueueDirectedEdgeedges(){//遍历图中的每一个顶点得到该顶点的邻接表遍历得到每一条边添加到队列中返回即可QueueDirectedEdgeallEdgesnewConcurrentLinkedQueue();for(intv0;vV;v){for(DirectedEdgeedge:adj[v]){allEdges.offer(edge);}}returnallEdges;}}最短路径有了加权有向图之后我们立刻就能联想到实际生活中的使用场景例如在一副地图中找到顶点a与地点b之间的路径这条路径可以是距离最短也可以是时间最短也可以是费用最小等如果我们把距离/时间/费用看做是成本那么就需要找到地点a和地点b之间成本最小的路径也就是我们接下来要解决的最短路径问题。定义在一副加权有向图中从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。性质路径具有方向性权重不一定等价于距离。权重可以是距离、时间、花费等内容权重最小指的是成本最低只考虑连通图。一副图中并不是所有的顶点都是可达的如果s和t不可达那么它们之间也就不存在最短路径为了简化问题这里只考虑连通图。最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条这里只需要找出一条即可。最短路径树给定一副加权有向图和一个顶点s以s为起点的一棵最短路径树是图的一副子图它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s树的每条路径都是有向图中的一条最短路径。最短路径树API设计松弛技术松弛这个词来源于生活一条橡皮筋沿着两个顶点的某条路径紧紧展开如果这两个顶点之间的路径不止一条还有存在更短的路径那么把皮筋转移到更短的路径上皮筋就可以放松了。松弛这种简单的原理刚好可以用来计算最短路径树。在我们的API中需要用到两个成员变量edgeTo和distTo分别存储边和权重。一开始给定一幅图G和顶点s我们只知道图的边以及这些边的权重其他的一无所知此时初始化顶点s到顶点s的最短路径的总权重disto[s]0顶点s到其他顶点的总权重默认为无穷大随着算法的执行不断的使用松弛技术处理图的边和顶点并按一定的条件更新edgeTo和distTo中的数据最终就可以得到最短路劲树。边的松弛放松边v-w意味着检查从s到w的最短路径是否先从s到v然后再从v到w如果是则v-w这条边需要加入到最短路径树中更新edgeTo和distTo中的内容edgeTo[w]表示v-w这条边的DirectedEdge对象distTo[w]distTo[v]v-w这条边的权重如果不是则忽略v-w这条边。顶点的松弛顶点的松弛是基于边的松弛完成的只需要把某个顶点指出的所有边松弛那么该顶点就松弛完毕。例如要松弛顶点v只需要遍历v的邻接表把每一条边都松弛那么顶点v就松弛了。Dijstra算法实现Disjstra算法的实现和Prim算法很类似构造最短路径树的每一步都是向这棵树中添加一条新的边而这条新的边是有效横切边pq队列中的权重最小的边。辅助类1. DirectedEdge----加权有向边2. EdgeWeightedDigraph----加权有向图3. IndexMinPriorityQueue----最小优先队列packagegraph.tu;publicclassIndexMinPriorityQueueTextendsComparableT{//存储堆中的元素privateT[]items;//保存每个元素在items数组中的索引pq数组需要堆有序privateint[]pq;//保存qp的逆序pq的值作为索引pq的索引作为值privateint[]qp;//记录堆中元素的个数privateintN;publicIndexMinPriorityQueue(intcapacity){this.items(T[])newComparable[capacity1];this.pqnewint[capacity1];this.qpnewint[capacity1];this.N0;//默认情况下队列中没有存储任何数据让qp中的元素都为-1for(inti0;iqp.length;i){qp[i]-1;}}//获取队列中元素的个数publicintsize(){returnN;}//判断队列是否为空publicbooleanisEmpty(){returnN0;}//判断堆中索引i处的元素是否小于索引j处的元素privatebooleanless(inti,intj){returnitems[pq[i]].compareTo(items[pq[j]])0;}//交换堆中i索引和j索引处的值privatevoidexch(inti,intj){//交换pq中的数据inttmppq[i];pq[i]pq[j];pq[j]tmp;//更新qp中的数据qp[pq[i]]i;qp[pq[j]]j;}//判断k对应的元素是否存在publicbooleancontains(intk){returnqp[k]!-1;}//最小元素关联的索引publicintminIndex(){returnpq[1];}//往队列中插入一个元素,并关联索引ipublicvoidinsert(inti,Tt){//判断i是否已经被关联如果已经被关联则不让插入if(contains(i)){return;}//元素个数1N;//把数据存储到items对应的i位置处items[i]t;//把i存储到pq中pq[N]i;//通过qp来记录pq中的iqp[i]N;//通过堆上浮完成堆的调整swim(N);}//删除队列中最小的元素,并返回该元素关联的索引publicintdelMin(){//获取最小元素关联的索引intminIndexpq[1];//交换pq中索引1处和最大索引处的元素exch(1,N);//删除qp中对应的内容qp[pq[N]]-1;//删除pq最大索引处的内容pq[N]-1;//删除items中对应的内容items[minIndex]null;//元素个数-1N--;//下沉调整sink(1);returnminIndex;}//删除索引i关联的元素publicvoiddelete(inti){//找到i在pq中的索引intkqp[i];//交换pq中索引k处的值和索引N处的值exch(k,N);//删除qp中的内容qp[pq[N]]-1;//删除pq中的内容pq[N]-1;//删除items中的内容items[k]null;//元素的数量-1N--;//堆的调整sink(k);swim(k);}//把与索引i关联的元素修改为为tpublicvoidchangeItem(inti,Tt){//修改items数组中i位置的元素为titems[i]t;//找到i在pq中出现的位置intkqp[i];//堆调整sink(k);swim(k);}//使用上浮算法使索引k处的元素能在堆中处于一个正确的位置privatevoidswim(intk){while(k1){if(less(k,k/2)){exch(k,k/2);}kk/2;}}//使用下沉算法使索引k处的元素能在堆中处于一个正确的位置privatevoidsink(intk){while(2*kN){//找到子结点中的较小值intmin;if(2*k1N){if(less(2*k,2*k1)){min2*k;}else{min2*k1;}}else{min2*k;}//比较当前结点和较小值if(less(k,min)){break;}exch(k,min);kmin;}}}Dijstra算法代码packagegraph.tu;importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedQueue;publicclassDijkstraSP{//索引代表顶点值表示从顶点s到当前顶点的最短路径上的最后一条边privateDirectedEdge[]edgeTo;//索引代表顶点值从顶点s到当前顶点的最短路径的总权重privatedouble[]distTo;//存放树中顶点与非树中顶点之间的有效横切边privateIndexMinPriorityQueueDoublepq;//根据一副加权有向图G和顶点s创建一个计算顶点为s的最短路径树对象publicDijkstraSP(EdgeWeightedDigraphG,ints){//初始化edgeTothis.edgeTonewDirectedEdge[G.V()];//初始化distTothis.distTonewdouble[G.V()];for(inti0;idistTo.length;i){distTo[i]Double.POSITIVE_INFINITY;}//初始化pqthis.pqnewIndexMinPriorityQueue(G.V());//找到图G中以顶点s为起点的最短路径树//默认让顶点s进入到最短路径树中distTo[s]0.0;pq.insert(s,0.0);//遍历pqwhile(!pq.isEmpty()){relax(G,pq.delMin());}}//松弛图G中的顶点vprivatevoidrelax(EdgeWeightedDigraphG,intv){for(DirectedEdgeedge:G.adj(v)){//获取到该边的终点wintwedge.to();//通过松弛技术判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v然后再由顶点v到顶点wif(distTo(v)edge.weight()distTo(w)){distTo[w]distTo[v]edge.weight();edgeTo[w]edge;//判断pq中是否已经存在顶点w如果存在则更新权重如果不存在则直接添加if(pq.contains(w)){pq.changeItem(w,distTo(w));}else{pq.insert(w,distTo(w));}}}}//获取从顶点s到顶点v的最短路径的总权重publicdoubledistTo(intv){returndistTo[v];}//判断从顶点s到顶点v是否可达publicbooleanhasPathTo(intv){returndistTo[v]Double.POSITIVE_INFINITY;}//查询从起点s到顶点v的最短路径中所有的边publicQueueDirectedEdgepathTo(intv){//判断从顶点s到顶点v是否可达如果不可达直接返回nullif(!hasPathTo(v)){returnnull;}//创建队列对象QueueDirectedEdgeallEdgesnewConcurrentLinkedQueue();while(true){DirectedEdgeeedgeTo[v];if(enull){break;}allEdges.offer(e);ve.from();}returnallEdges;}}测试查找最短路径,0-6的最短路径packagegraph.tu;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Queue;publicclassDijkstraSPTest{publicstaticvoidmain(String[]args)throwsException{//创建一副加权有向图BufferedReaderbrnewBufferedReader(newInputStreamReader(DijkstraSPTest.class.getClassLoader().getResourceAsStream(min_route_test.txt)));inttotalInteger.parseInt(br.readLine());EdgeWeightedDigraphGnewEdgeWeightedDigraph(total);intedgeNumbersInteger.parseInt(br.readLine());for(inti1;iedgeNumbers;i){Stringlinebr.readLine();//4 5 0.35String[]strsline.split( );intvInteger.parseInt(strs[0]);intwInteger.parseInt(strs[1]);doubleweightDouble.parseDouble(strs[2]);DirectedEdgeenewDirectedEdge(v,w,weight);G.addEdge(e);}//创建DijkstraSP对象查找最短路径树DijkstraSPdijkstraSPnewDijkstraSP(G,0);//查找最短路径,0-6的最短路径QueueDirectedEdgeedgesdijkstraSP.pathTo(6);//遍历打印for(DirectedEdgeedge:edges){System.out.println(edge.from()-edge.to() edge.weight());}}}