最短路径算法java

上次写的博客,自己发现存在着一个比较大的问题,讲解的没有透彻。 还是举昨天的Dijkstra算法来讲吧。 昨天讲到是每一个循环找出一个点,花式这么说,但是后来想了想,发现其实自己有一个地方没讲清楚,那就是,找出一个点的之后的操作,上次自己只是简单的略过了,但是昨天自己回去想了想为什么只是排查上次查找的那个点呢,而不是排查之前已经已经查找出来的点呢,之后自己猜知道,第一次排查的时候就已经查找出了最近的点,而其他点与初始原点的距离是不变的,所以,如果之后的点会出现比之前还要短的路径,那么只能通过之前查找过的点来查看是否有另外的路径通往现在的点,并且还比之前的小,如果可以,那么就替换,否则不动,所以就不用排查之前已经遍历过的每个点。 下面我用几个图来演示一下

这里对不起了,用的别人的图 首先我们以1位初始点开始找,这时候我们发现1的附近只存在1---->2和1----->3这两条路径那么我们只需要选出这两者当中最短的一条保存那就是1---->2这条路径,这时候我们并没有保存其他的路径,

所以就以2为起点开始发散,这时候我们发现2附近存在两条路径分别为2---->4和2---->3这时候我们存储其中最短的一条,即为2---->4这条路径,这时候存储4这个点。

这次循环我们就以4为点开始发散,这时候重点来了,4附近存在3条路,分别为4---->3和4---->5和4------>6,这时候我们发现,最短路径即为4---->3这条路径,**这里就是重点 **之前我们就已经发现了2---->3这条路的时候,但是我们并没有选择那条路,而是在之后选择,正是如此。所以希望对大家有所帮助。顺便附上之前看了同学之后改进过的算法,但主要运用的是spfa算法。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class minpath第三版 {
	static int leng[];
	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n=(int)in.nval;in.nextToken();int m=(int)in.nval;
		List<node>list[]=new ArrayList[n];
		for(int i=0;i<n;i++)
		{
			list[i]=new ArrayList<>();
		}
	    leng=new int[n];
		boolean jud[]=new boolean[n];
		for(int i=1;i<n;i++) {leng[i]=Integer.MAX_VALUE;}
		for(int i=0;i<m;i++)
		{
			in.nextToken();int u=(int)in.nval;
			in.nextToken();int v=(int)in.nval;
			in.nextToken();int l=(int)in.nval;
			list[u-1].add(new node(v-1, l));					
		}
		Queue<Integer>q1=new ArrayDeque<Integer>();
		q1.add(0);
		while(!q1.isEmpty())
		{
			int x=q1.poll();
	        boolean judgel=false;
			
		   for(int i=0;i<list[x].size();i++)//遍历
			{
			      /*if(leng[list[x].get(i).x]==Integer.MAX_VALUE) //首先第一种情况就是两者之间没有直接的路径进行连接,所以长度才是之前定义的最大值
			    	                                            //那么就开始遍历之前已经遍历出来的点
			      { 
			    	  leng[list[x].get(i).x]=leng[x]+list[x].get(i).leng;
			    	  q1.add(list[x].get(i).x);
			    	  judgel=true;
			      }*/
				  if(leng[list[x].get(i).x]>leng[x]+list[x].get(i).leng)
				  {
					  leng[list[x].get(i).x]=leng[x]+list[x].get(i).leng;
					  q1.add(list[x].get(i).x);
					  judgel=true;
				  }		
			}
			if(judgel) 
			{
				q1.add(x);
			}
		}
		for(int i=1;i<n;i++)
		{
			out.println(leng[i]);
		}
		out.flush();
	}
	static class node
	{
		int x;
		int leng;
		public node(int x,int leng)
		{
			this.x=x;
			this.leng=leng;
		}
	}
}

本人很菜,如有不足,请大家指教。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python爬虫将数据写入csv文件乱码

    养成习惯,先赞后看!!! 出现乱码根本原因就是编码方式不对,但是博主自己尝试了三种编码方式终于找到了最合适的。

    萌萌哒的瓤瓤
  • 最短路径Dijkstra算法的简单实现

    最近刷题一连碰到好几道关于最短路径的问题自己一开始用深搜过了之后也就没怎么 管,但是之后的好几道用深搜都超时,之后查了资料才知道这种最短路径的问题一般使用广搜的...

    萌萌哒的瓤瓤
  • 剑指offer(25-30)题解

    萌萌哒的瓤瓤
  • flutter InkWell实现水波纹点击效果

    在flutter 开发中用InkWell或者GestureDetector将某个组件包起来,已添加点击事件。

    砸漏
  • UIScrollView的一步步实现1 简介1.1 工作原理1.2 UIScrollView常见的几个重要控件1.3 UIScrollView常见的重要属性1.4 手工代码实现拖动2 三个重要属性的进

    stanbai
  • 【2018秋招iOS面试总结】(渣渣本科生)

    本人是非985211学校,非计算机专业,技术一般,基础较差。 最开始秋招的时候,一线互联网基本上都投了,但是很多都被刷了,有的是刷了学校,有的是刷了四级(我四级...

    牛客网
  • Code Forces 644B Processing Queries

    B. Processing Queries time limit per test5 seconds memory limit per test256 ...

    ShenduCC
  • python算法与数据结构-希尔排序(35)

      希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按...

    Se7eN_HOU
  • C++之运算符重载(二)

    https://blog.csdn.net/zy010101/article/details/105240318

    zy010101
  • C++学习笔记 类型声明

    类型别名 typedef关键字 typedef关键字是继承自C语言的特性,利用它我们可以为一个类型起别名,一般用于将复杂类型简化。举个简单的例子,将int类型定...

    乐百川

扫码关注云+社区

领取腾讯云代金券