Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      

微软编程比赛里面的一道难度系数5%的编程题目如下:

image
image

Dijkstra算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用Dijkstra算法来解决这个问题。

image

根据图来建立权值矩阵:

1int[][] W = { { 0, 1, , -1, -1, -1-1-1 -1}, { 1, 0, 3, 7, 5, -1-1-1-1}, { 5, 3, 0, -1, 1, 7, -1-1-1-1 }, { -1, 7, -1, 0, 2, -1,3-1-1 }, { -1, 5, 1, 2, 0, 3, 6, 9-1}, {-1-1-1, 36-1, 0 2, 7} {-1-1-1-1952, 0, 4} {-1-1-1-1-1-1, 7, 4, 0} };
2// (-1表示两边不相邻,权值无限大)

最终实现如下(java):

 1package wxt;
 2
 3import java.util.ArrayList;
 4import java.util.List;
 5import java.util.Scanner;
 6
 7//这个算法用来解决无向图中任意两点的最短路径  
 8public class Dijkstra {
 9  public static int dijkstra(int[][] W1, int start, int end) {  
10      boolean[] isLabel = new boolean[W1[0].length];// 是否标号  
11      int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈  
12      int i_count = -1;//栈的顶点  
13      int[] distance = W1[start].clone();// v0到各点的最短距离的初始值  
14      int index = start;// 从初始点开始
15      int presentShortest = 0;//当前临时最短距离  
16
17      indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
18      isLabel[index] = true;  
19        
20      while (i_count<W1[0].length) {  
21          // 第一步:标号v0,即w[0][0]找到距离v0最近的点  
22
23          int min = Integer.MAX_VALUE;  
24          for (int i = 0; i < distance.length; i++) {  
25              if (!isLabel[i] && distance[i] != -1 && i != index) {  
26                  // 如果到这个点有边,并且没有被标号  
27                  if (distance[i] < min) {  
28                      min = distance[i];  
29                      index = i;// 把下标改为当前下标  
30                  }  
31              }  
32          }  
33          if (index == end) {//已经找到当前点了,就结束程序  
34              break;  
35          }  
36          isLabel[index] = true;//对点进行标号  
37          indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
38          if (W1[indexs[i_count - 1]][index] == -1 
39                  || presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {  
40              // 如果两个点没有直接相连,或者两个点的路径大于最短路径  
41              presentShortest = distance[index];  
42          } else {  
43              presentShortest += W1[indexs[i_count - 1]][index];  
44          }  
45
46          // 第二步:将distance中的距离加入vi  
47          for (int i = 0; i < distance.length; i++) {  
48              // 如果vi到那个点有边,则v0到后面点的距离加  
49              if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达,则现在可达了  
50                  distance[i] = presentShortest + W1[index][i];  
51              } else if (W1[index][i] != -1 
52                      && presentShortest + W1[index][i] < distance[i]) {  
53                  // 如果以前可达,但现在的路径比以前更短,则更换成更短的路径  
54                  distance[i] = presentShortest + W1[index][i];  
55              }  
56
57          }  
58      }  
59      //如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径  
60      return distance[end] - distance[start];  
61  }  
62  private static class Island{
63	  public int x,y;
64  }
65  public static void main(String[] args) {  
66	  ArrayList<Island> arr=new ArrayList<Island>();
67      // 建立一个权值矩阵  
68      
69      int [][] Test={
70    		  {0,1,4},{1,0,1},{4,1,0}
71      };
72      Scanner input=new Scanner(System.in);
73      int num=input.nextInt();
74      for (int i = 0; i < num; i++) {
75    	  Island island=new Island();
76    	  island.x=input.nextInt();
77    	  island.y=input.nextInt();
78          arr.add(island);
79	}
80      int [][] t=new int[num][num];
81      for (int i = 0; i < t.length; i++) {
82    	  for (int j = 0; j < t.length; j++) {
83			t[i][j]=Math.min(Math.abs(arr.get(i).x-arr.get(j).x), Math.abs(arr.get(i).y-arr.get(j).y));
84		}
85		
86	}
87      System.out.println(dijkstra(t, 0,num-1));  
88
89  }  
90}


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:用Dijkstra算法求解无向图的最短路径
作者:潘建锋
原文:HTTPS://strikefreedom.top/solve-shortest-path-via-dijkstra-algorithm

关于留言和评论

如果您对本文《用Dijkstra算法求解无向图的最短路径》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~