专栏首页java,python,数据结构,算法最短路径Dijkstra算法的简单实现

最短路径Dijkstra算法的简单实现

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

而且实现起来有好几种算法,用的最多的就是Dijkstra和Flody这两种算法,这两者的主要区别就是Dijkstra主要用来解决一个初始化的点到所有其他点的所有最短路径,而Flody主要用来解决确定的两点之间所存在的最短路径,今天就先讲解一下Dijkstra算法

假设有n个点,那么Dijkstra算法会进行n-1次循环,每次循环找出原点到其他另外所有相邻的点中最短的一个点,注意这里必须是相邻的点,之后会将这个点放入原点的集合中,因为已经找到该点的最短路径了,之后再一次循环,之后的循环就不单单是查找之前已经找到的点的相邻点中的最短路径了,而是找到之前集合中所有已经找到最短路径的点的最短相邻点,然后判断并选择出其中最短的路径及其点,重复这种操作,最后就能查找到原点到所有其他的点的最短路径了。

其实这里面还用到了几何知识,就比如说三角形的知识,比如说a到b中间如果一开始直接有一条路我们记作a->b,但是之后经过搜索之后发现能通过另外一个点c到达点b,并且路径长还小于之前的路径长即a->b > a->c->b的。

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.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class minpath第二版 {
	public static int n;//存储所有的点
	public static int m;//存储所有的边
	public static int map[][];//存储有向图中的所有有向边
	public static int visit[];//判断每个点是否已经被访问过
	public 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();n=(int) in.nval;
		in.nextToken();m=(int) in.nval;
		List<Integer>list1[]=new ArrayList[n];
		for(int i=0;i<n;i++)
			list1[i]=new ArrayList<>();//存储每个点的邻接点
		map=new int [n][n];//初始化每个数组
		visit=new int [n];
		leng=new int [n];
		for(int i=0;i<n;i++)
			visit[i]=0;
		for(int i=0;i<n;i++)//初始化数组并赋值为最大的值,原因是之后肯定会有最短路径与之比较并肯定会将之替换
		{
			leng[i]=Integer.MAX_VALUE;
			for(int j=0;j<n;j++)
			{
				map[i][j]=Integer.MAX_VALUE;
			}
		}
		for(int i=0;i<m;i++)//存入各顶点的相邻结点及其有向路径长
		{
			in.nextToken();int n1=(int) in.nval;
			in.nextToken();int n2=(int) in.nval;
			in.nextToken();int n3=(int) in.nval;
			map[n1-1][n2-1]=n3;
			list1[n1-1].add(n2-1);
		}
		Queue<node>queue=new PriorityQueue<>(compare);//这个优先队列用来存储每次查找出来的最短的最短的点,并将它抛出,所以循环的终止条件是优先队列为空
		queue.add(new node(0,0));
		while(!queue.isEmpty())
		{
			node node1=queue.poll();
			if(visit[node1.x]==0)
			{
				visit[node1.x]=1;
				for(int i=0;i<list1[node1.x].size();i++)//查询抛出点的所有邻接点
				{
					if(map[node1.x][list1[node1.x].get(i)]!=Integer.MAX_VALUE&&visit[list1[node1.x].get(i)]==0)//该邻接点需要不是最大值,就意味着两者之间存在边,并且还没有被访问过
					{
						if(leng[list1[node1.x].get(i)]>node1.length+map[node1.x][list1[node1.x].get(i)])//判断长度是否与之前的路径短,如果短,则替换
						{
							leng[list1[node1.x].get(i)]=node1.length+map[node1.x][list1[node1.x].get(i)];
							queue.add(new node(list1[node1.x].get(i),node1.length+map[node1.x][list1[node1.x].get(i)] ));//加入该点,重复循环
						}
					}
				}
				
			}
		}
		for(int i=1;i<n;i++)
			out.println(leng[i]);
		out.flush();
	}
	static Comparator<node>compare=new Comparator<node>() {//将各个点按长度从小到大排列

		@Override
		public int compare(node o1, node o2) {
			// TODO Auto-generated method stub
			return o1.length-o2.length;
		}
		
	};
	static class node
	{
		int x;
		int length;
		public node(int x,int length) {
			// TODO Auto-generated constructor stub
			this.x=x;
			this.length=length;
		}
	}

}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    萌萌哒的瓤瓤
  • 最短路径算法java

    上次写的博客,自己发现存在着一个比较大的问题,讲解的没有透彻。 还是举昨天的Dijkstra算法来讲吧。 昨天讲到是每一个循环找出一个点,花式这么说,但是后...

    萌萌哒的瓤瓤
  • 使用cookie来记录用户登录次数,为何次数不更新

    作者也是刚刚接触cookie以及session 首先贴上别人对cookie以及session的理解: cookie 和session 的区别:

    萌萌哒的瓤瓤
  • 基于opentracing + jaeger 实现全链路追踪

    当代互联网服务,通常都是用复杂,大规模分布式集群来实现,微服务化,这些软件模块分布在不同的机器,不同的数据中心,由不同团队,语言开发而成。因此,需要工具帮助理解...

    orientlu
  • 地表最简单安装MySQL及配置的方法,没有之一

    第一步下载我的压缩包 链接:https://pan.baidu.com/s/1EE40dU0j2U1d-bAfj7TeVA 提取码:n25c 复制这段内容...

    风骨散人Chiam
  • CSS系列之教你几招小技巧,让开发更高效

    俗话说「人靠衣装马靠鞍」,一个网页的漂亮与否CSS起到了很大的作用。它能够帮助我们进行美化。因此 CSS 在前端开发中的地位不用多说。

    六小登登
  • 深入理解Java常用类----String(二)

         上篇介绍了String类的构造器,获取内部属性等方法,最后留下了最常用的局部操作函数没有介绍,本篇将接着上篇内容,从这些最常见的函数的操作说起,看看我...

    Single
  • [MachineLearning]tesseract使用

    https://github.com/tesseract-ocr/tesseract

    wOw
  • 在Mono 2.8上部署ASP.NET MVC 2

    Mono 2.8发布:C#4.0和更好的性能,我们知道Mono 2.8对ASP.NET MVC 2的完全支持,下面我们就来测试下在Mono 2.8上部署ASP....

    张善友
  • 收集的网络上大型的开源图像处理软件代码(提供下载链接)

    要写好一个图像处理软件,仅靠自己看书是完全不够的,要多方面学习,借鉴前人的经验,要集思广益、多面出击。如今网络发达,图像学的资料其实也到处都是。只是...

    用户1138785

扫码关注云+社区

领取腾讯云代金券