四川淘宝网站建设方案,seo引擎搜索网址,昆明网站设计能实现什么功能,在线代理网址目录 一、什么是Dijkstra算法二、算法基本步骤三、java代码四、拓展#xff08;无向图的Dijkstra算法#xff09; 一、什么是Dijkstra算法
Dijkstra算法的核心思想是通过逐步逼近的方式#xff0c;找出从起点到图中其他所有节点的最短路径。算法的基本步骤如下#xff1a;… 目录 一、什么是Dijkstra算法二、算法基本步骤三、java代码四、拓展无向图的Dijkstra算法 一、什么是Dijkstra算法
Dijkstra算法的核心思想是通过逐步逼近的方式找出从起点到图中其他所有节点的最短路径。算法的基本步骤如下
举个例子 如图所示的V1-V6六个点及他们的有向权重连线现在我们假设从V1点出发,画出从顶点V1到其余各点最短路径的过程
首先我们将V1拿出来V1能通向V2和V3,V1到V1的距离我们可以看成0V1到V2的距离是10V1到V3的距离是12V1不能直接到达V4V5V6我们可以看成是无穷大那么V1的上一个结点是V1V2和V3的上一个结点也是V1。V4V5V6此是没有连接结点记为-1得到如下表格 然后根据距离数组{0,10,12,∞,∞,∞}找出数组中距离最小的值即V2的10我们将V2拿出来放到数组S中,则数组V中还剩余{V3,V4,V5,V6}现在我们取出了V1V2V1到V1和V2的位置还是没有变取出V2后V1到V3没有新的通路所以距离还是12所以V3的上一个点还是V1V4和V5是可以根据V2进行跟新的V4101626,V5102535我们取出了V1V2到V6还是没有路线可以走所以更新之后的表格如下 我们距离数组{0,10,12,26,35,∞}中选取最小值即12的V3结点加入数组S中数组V为{V4,V5,V6}现在加入的结点为V1、V2、V3现在V1到V2的路线多出来V1-V3-V2但是总长度是15比原本的10要大啊所以不做变化V1到V3的距离还是12V1-V4有两条路V1-V2-V4和V1-V3-V4跟新后的V1-V3-V4距离是24比原来的26更短所以替换之然后V4上一个点的坐标就变成了V3我们再看一下V1-V5V1-V2-V5和V1-V3-V2-V5显然还是原本的35是最短距离V1-V6的路径是V1-V3-V6距离是20更新表格 我们在数组{0,10,12,24,35,20}可以看出在去掉V1、V2、V3之后最小的点是V6的20所以我们将V6加入到数组S中V1到V1、V2、V3的距离保持不变V1到V4的因为增加了V6所以多出来一条V1-V3-V6-V4距离是22比之前的24小进行更新所以V4的上一个结点变成V6然后V1到V5多增加路线V1-V3-V6-V5总体距离变成30比之前的35要小更新表格V5的上一个结点变成V6跟新后的表格 从数组V中取出距离最短的值V4放入数组S中此时V1到V1、V2、V3、V4的距离保持不变V1-V5的距离多了一条V1-V3-V6-V4-V5路径从29比以前的30要短更新表格所以V5的上一个结点的V4V1-V6保持不变更新后表格如下 将最后一个点V5添加到数组S中V5没有到其他点的新路径所以dist[]和path[]数组不变。
如果想要知道V1到V6的距离
先看path[],V6的上一个结点时V3V3的上一个结点是V1所以V1到V6的路径是V1-V3-V6由dist[]数组得知距离权重是20
如果想要知道V1到V5的距离
先看path[],V5的上一个结点时V4V4的上一个结点时V6V6的上一个结点时V3V3的上一个结点是V1所以V1到V5的路径是V1-V3-V6-V4-V5由dist[]数组得知距离权重是29
其他的以此类推
二、算法基本步骤
初始化
创建一个最短路径信息数组shortPath[x][3]每一个一维数组含义为当前结点、该节点到此节点的最短路径、起始节点。初始化shortPath数组shortPath[x][0]当前节点编号、shortPath[x][1]最短路径、shortPath[x][2]起始结点编号初始化优先队列将起始节点的所有邻接点加入到优先队列中结点信息使用Ownership类属性值{time、nodeIndex、weight}。创建优先队列优先队列按照结点的权重值优先出队 PriorityQueue。创建优先队列的比较器OwnershipCustomerComparator类通过weight大小进行优先出队。
流程
优先队列为空则退出遍历优先队列将队列中time版本对应的结点信息值写入shortPath中。每次拿到最新路径长度newWeightmatrix[up - 1][ownership.nodeIndex] shortPath[up - 1][1]起始节点最短路径起始节点到当前节点一条边的权重如果当前结点未被初始化则直接将newWeight写入shortPath数组中如果当前节点已经被写过最短路径则直接略过当前newWeight即可这里有一个dtx变量记录当前优先队列中结点是否被写如果shortPath用于time版本。遍历优先队列需要出队将权重最小的结点出队将该节点下的所有邻接点拿出做以下操作步骤 需要是出对节点的邻接点邻接点在shortPath表中的最短路径未被初始化还是无穷大将结点信息写入最短路径为出对节点权重出对节点到达该邻接点的权重查看该邻接点是否出现在优先队列中。在优先队列中则更新shortPath数组以及优先队列中该结点的权重以及起始节点的信息。优先队列中没有Math.min(newWeight, shortPath[i][1])取最优路径写入
三、java代码
代码地址GitHub
算法代码
public class Dijkstra {private Queue visited;int[] distance;public Dijkstra(int len) {// TODO Auto-generated constructor stubvisited new LinkedList();distance new int[len];}private int getIndex(Queue q, int[] dis) {int k -1;int min_num Integer.MAX_VALUE;for (int i 0; i dis.length; i) {if (!q.contains(i)) {if (dis[i] min_num) {min_num dis[i];k i;}}}return k;}public void dijkstra(int[][] weight, Object[] str, int v) {HashMap path;path new HashMap();for (int i 0; i str.length; i)path.put(i, );//初始化路径长度数组distancefor (int i 0; i str.length; i) {path.put(i, path.get(i) str[v]);if (i v)distance[i] 0;else if (weight[v][i] ! -1) {distance[i] weight[v][i];path.put(i, path.get(i) -- str[i]);} elsedistance[i] Integer.MAX_VALUE;}visited.add(v);while (visited.size() str.length) {int k getIndex(visited, distance);//获取未访问点中距离源点最近的点visited.add(k);if (k ! -1) {for (int j 0; j str.length; j) {//判断k点能够直接到达的点if (weight[k][j] ! -1) {//通过遍历各点比较是否有比当前更短的路径有的话则更新distance并更新path。if (distance[j] distance[k] weight[k][j]) {distance[j] distance[k] weight[k][j];path.put(j, path.get(k) -- str[j]);}}}}}for (int h 0; h str.length; h) {System.out.printf(str[v] -- str[h] : distance[h] );if (distance[h] Integer.MAX_VALUE)System.out.print(str[v] -- str[h] 之间没有可通行路径);elseSystem.out.print(str[v] - str[h] 之间有最短路径具体路径为 path.get(h).toString());System.out.println();}visited.clear();}
}测试代码
public static void main(String[] args) {// TODO Auto-generated method stubint[][] weight {{0, 10, 12, -1, -1, -1},{-1, 0, -1, 16, 25, -1},{4, 3, 0, 12, -1, 8},{-1, -1, -1, 0, 7, -1},{-1, -1, -1, -1, 0, -1},{-1, -1, -1, 2, -1, 0}};String[] str {V1, V2, V3, V4, V5, V6};int len str.length;Dijkstra dijkstra new Dijkstra(len);//依次让各点当源点并调用dijkstra函数for (int i 0; i str.length; i) {dijkstra.dijkstra(weight, str, i);}}测试结果
四、拓展无向图的Dijkstra算法
有向图问题解决了无向图道理和有向图类似例如如下的无向图找出V1到其他个点的最短路径 我们只需要在Test类中定义一个无向图数组
int[][] undirected_weight {{0,3,-1,7,-1},{3,0,4,2,-1},{-1,4,0,5,4},{7,2,5,0,6},{-1,-1,4,6,0}};
String[] str {V1, V2, V3, V4, V5};最后运行结果 觉得有用的话还请多多点赞、收藏、评论!!!
