文档章节

用Dijkstra算法求解无向图的最短路径

潘少online
 潘少online
发布于 2015/04/16 21:18
字数 866
阅读 411
收藏 2

  Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      微软编程比赛里面的一道难度系数5%的编程题目如下:
这里写图片描述
这里写图片描述   Dijkstra算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用Dijkstra算法来解决这个问题。 这里写图片描述   根据图来建立权值矩阵: int[][] W = { { 0, 1, 5, -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, 3,6,-1, 0, 2, 7} {-1,-1,-1,-1,9,5,2, 0, 4} {-1,-1,-1,-1,-1,-1, 7, 4, 0} };(-1表示两边不相邻,权值无限大)

java代码如下:

package wxt;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//这个算法用来解决无向图中任意两点的最短路径  
public class Dijkstra {
  public static int dijkstra(int[][] W1, int start, int end) {  
      boolean[] isLabel = new boolean[W1[0].length];// 是否标号  
      int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈  
      int i_count = -1;//栈的顶点  
      int[] distance = W1[start].clone();// v0到各点的最短距离的初始值  
      int index = start;// 从初始点开始
      int presentShortest = 0;//当前临时最短距离  

      indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
      isLabel[index] = true;  
        
      while (i_count<W1[0].length) {  
          // 第一步:标号v0,即w[0][0]找到距离v0最近的点  

          int min = Integer.MAX_VALUE;  
          for (int i = 0; i < distance.length; i++) {  
              if (!isLabel[i] && distance[i] != -1 && i != index) {  
                  // 如果到这个点有边,并且没有被标号  
                  if (distance[i] < min) {  
                      min = distance[i];  
                      index = i;// 把下标改为当前下标  
                  }  
              }  
          }  
          if (index == end) {//已经找到当前点了,就结束程序  
              break;  
          }  
          isLabel[index] = true;//对点进行标号  
          indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
          if (W1[indexs[i_count - 1]][index] == -1 
                  || presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {  
              // 如果两个点没有直接相连,或者两个点的路径大于最短路径  
              presentShortest = distance[index];  
          } else {  
              presentShortest += W1[indexs[i_count - 1]][index];  
          }  

          // 第二步:将distance中的距离加入vi  
          for (int i = 0; i < distance.length; i++) {  
              // 如果vi到那个点有边,则v0到后面点的距离加  
              if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达,则现在可达了  
                  distance[i] = presentShortest + W1[index][i];  
              } else if (W1[index][i] != -1 
                      && presentShortest + W1[index][i] < distance[i]) {  
                  // 如果以前可达,但现在的路径比以前更短,则更换成更短的路径  
                  distance[i] = presentShortest + W1[index][i];  
              }  

          }  
      }  
      //如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径  
      return distance[end] - distance[start];  
  }  
  private static class Island{
	  public int x,y;
  }
  public static void main(String[] args) {  
	  ArrayList<Island> arr=new ArrayList<Island>();
      // 建立一个权值矩阵  
      
      int [][] Test={
    		  {0,1,4},{1,0,1},{4,1,0}
      };
      Scanner input=new Scanner(System.in);
      int num=input.nextInt();
      for (int i = 0; i < num; i++) {
    	  Island island=new Island();
    	  island.x=input.nextInt();
    	  island.y=input.nextInt();
          arr.add(island);
	}
      int [][] t=new int[num][num];
      for (int i = 0; i < t.length; i++) {
    	  for (int j = 0; j < t.length; j++) {
			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));
		}
		
	}
      System.out.println(dijkstra(t, 0,num-1));  

  }  
}  

© 著作权归作者所有

潘少online
粉丝 12
博文 58
码字总数 107019
作品 2
深圳
程序员
私信 提问
这个代码在提交OJ时提示输出超限,求大神们解决

题目描述 由n个点和m条无向边构成的无向连通图,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 请用Dijkstr...

Arice徐新凯
2014/06/16
1K
0
MADlib——基于SQL的数据挖掘解决方案(28)——图算法之单源最短路径

图算法指利用特制的线条算图求得答案的一种简便算法。无向图、有向图和网络能运用很多常用的图算法,其中主要包括各种遍历算法(这些遍历类似于树的遍历),寻找最短路径的算法,寻找网络中最...

wzy0623
2018/03/15
0
0
HAWQ + MADlib 玩转数据挖掘之(十)——图算法之单源最短路径

一、图算法简介 1. 定义 在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一点开始,连结相关线段上的点,连线与表示...

wzy0623
2017/08/17
0
0
数学:Dijkstra算法

一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的...

pricker
2015/09/12
123
0
最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee
2016/01/14
3.3K
1

没有更多内容

加载失败,请刷新页面

加载更多

skywalking(容器部署)

skywalking(容器部署) 标签(空格分隔): APM [toc] 1. Elasticsearch SkywalkingElasticsearch 5.X(部分功能报错、拓扑图不显示) Skywalking需要Elasticsearch 6.X docker network create......

JUKE
7分钟前
1
0
解决Unable to find a single main class from the following candidates [xxx,xxx]

一、问题描述 1.1 开发环境配置 pom.xml <plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-plugin</artifactId><!--一定要对上springboot版本号,因......

TeddyIH
7分钟前
0
0
Dubbo服务限制大数据传输抛Data length too large: 13055248, max payload: 8388608解决方案

当dubbo服务提供者向消费层传输大数据容量数据时,会受到Dubbo的限制,报类似如下异常: 2019-08-23 11:04:31.711 [ DubboServerHandler-XX.XX.XX.XXX:20880-thread-87] - [ ERROR ] [com.al...

huangkejie
10分钟前
0
0
HashMap和ConcurrentHashMap的区别

为了线程安全,ConcurrentHashMap 引入了一个 “分段锁” 的概念。具体可以理解把一个大的 map 拆分成 N 个小的 Map 。最后再根据 key.hashcode( )来决定放到哪一个 hashmap 中去。 hashmap ...

Garphy
11分钟前
0
0
购买SSL证书需要注意哪些问题

为了保障网站的基本安全,为网站部署SSL证书,已经是一种常态了。各大浏览器对于安装了SSL证书的网站会更友好,并且不会发出“不安全”的提示。部署SSL证书之前首先得去给网站购买一个SSL证书...

安信证书
40分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部