最短路径算法java
最短路径算法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;
}
}
}本人很菜，如有不足，请大家指教。