图论Dijkstra算法模板和应用

算法模板和应用"/>

图论Dijkstra算法模板和应用

一、使用条件

目的是求图中一个节点（k）到某一个节点的最短距离,或者最大距离，使用Dijkstra算法要求图是加权有向图且没有负权重的边。

输入：加权有向图

输出：一个数组disTo ，代表k到i节点的最短距离。

模板如下

class State{int id;int disFromStart;State(int id,int disFromStart){this.id=id;this.disFromStart=disFromStart;}}int[] dijkstra(int start,List<int[]>[] grahp){int[] disTo=new int[grahp.length];Arrays.fill(disTo,Integer.MAX_VALUE);disTo[start]=0;PriorityQueue<State> pq=new PriorityQueue<>((a,b)->{return a.disFromStart-b.disFromStart;});pq.offer(new State(start,0));while(!pq.isEmpty()){State curNode=pq.poll();int curNodeID=curNode.id;int StartdiscurNode=curNode.disFromStart;if(disTo[curNodeID]<StartdiscurNode) continue;for(int[] linju:grahp[curNodeID]){int nextNodeID=linju[0];int disnextNode=linju[1]+disTo[curNodeID];if(disTo[nextNodeID]<=disnextNode){continue;}else{disTo[nextNodeID]=disnextNode;pq.offer(new State(nextNodeID,disnextNode));}}}return disTo;}

二、应用范围

leetcode743,1631,1514,787

一般有向加权图的输入是三元组[（u，v，w）],代表u到v这条边的权重为w，记录一下三元组转为图的模板。

List<int[]>[] grahp=new LinkedList[n+1];for(int i=1;i<n+1;i++){grahp[i]=new LinkedList<>();}for(int[] edges:times){int from=edges[0];int to=edges[1];int w=edges[2];grahp[from].add(new int[]{to,w});}

times为输入的三元组数组