java无权图求最短路径_求有权图和无权图的最短路径

无权图的最短路径

思路：无权图的最短路径也就是要求两点之间最少几跳可达，那么我们可以这样，用广度遍历，从起点开始一层层遍历，如果第一次遍历到终点，那么肯定是最短路径。

public static void findPath(int start,int end)

{

//创建一个队列来存储

LinkedList< VNode> queue=new LinkedList();

queue.offer(nodes[start]);

while(!queue.isEmpty())

{

VNode vnode=queue.peek();

isVisit[vnode.index]=true;

BNode bnode=vnode.bnode;

//如果结束点已经访问 跳出循环

if(isVisit[end])

break;

//如果他的邻节点都访问或者没有邻节点 跳出循环

while(bnode!=null)

{

//如果邻节点还没被访问访记录他的上一节点，否则不进行记录。这样的话即使到了下一跳有这个顶点，记录的也是更的短路径，比如说起点A 邻节点有BCD B的邻节点是C，此时遍历A的邻节点C的时候，就记录C的上一节点是A，下次遍历B的领节点，因为C已经被访问，所以C记录的上一节点还是A，这样就保证了最短路径。

if(!isVisit[bnode.index])

{

//用于记录路径

nodes[bnode.index].before=vnode;

queue.offer(nodes[bnode.index]);

isVisit[bnode.index]=true;

}

bnode=bnode.next;

}

queue.pop();

}

}

public static void printPath(int end)

{

VNode node=nodes[end];

int count=0;

String path="";

while(node!=null)

{

path=node.index+path;

node=node.before;

count++;

}

System.out.println(path+"长度为:"+(count-1));

}

Dijkstra求有权图最短路径

Dijkstra思路：依次找到最短路径，比如起点A，先找到距离A路径最短的点，比如B，AB路径长为1，这时候，接着往下找比大于等于1的最短路径。通俗讲就是小明很贪心，每一次都找挑最短路径。

import java.util.Scanner;

public class Dijkstra {

public static void main(String[] args) {

final int MAX=Integer.MAX_VALUE;

Scanner in=new Scanner(System.in);

int vNum=in.nextInt();

int edgeNum=in.nextInt();

//二维数值用来表示图

int graphic[][]=new int [vNum][vNum];

//flag[v][w]标识 从v0到v点 w是不是在路径上，用于记录路径

boolean [][] path=new boolean [vNum][vNum];

//标识是否访问过

boolean [] isVisit=new boolean[vNum];

//v0到各点的最短路径

int distance[]=new int [vNum];

//进行初始化，任意两个点的距离无限大

for (int i = 0; i

for (int j = 0; j < vNum; j++) {

graphic[i][j]=MAX;

}

}

//读取数据，设置权值

for (int i = 0; i < edgeNum; i++) {

graphic[in.nextInt()][in.nextInt()]=in.nextInt();

}

//起点

int v0=in.nextInt();

//结束点

int end=in.nextInt();

in.close();

//进行初始化

isVisit[v0]=true;

for (int i = 0; i < distance.length; i++) {

distance[i]=graphic[0][i];

if(graphic[v0][i]

{

path[i][i]=true;

path[i][v0]=true;

}

}

int v=-1;

//要找到vNum-1个顶点，循环次数为vNum-1

for (int i = 1; i < vNum; i++) {

int min=Integer.MAX_VALUE;

//遍历找到目前v0到其他点的最短距离的点,依次找到离起点最近的点

for (int j = 0; j < vNum; j++) {

if(!isVisit[j]&&distance[j]

{

min=distance[j];

v=j;

}

}

isVisit[v]=true;

//新的点v加入，重新更新从v0到其他点的最短距离

for (int k = 0; k < distance.length; k++) {

if(!isVisit[k]&&graphic[v][k]min+graphic[v][k])

{

distance[k]=min+graphic[v][k];

//当前的路径是从v到w，所以到v0到v的最短路径上的点也是v0到w上的点

System.arraycopy(path[v], 0, path[k], 0, path[v].length);

path[k][k]=true;

}

}

}

System.out.print("路径为：");

for (int i = 0; i < vNum; i++) {

if(path[end][i])

System.out.print(i+" ");

}

System.out.println("路径长为"+distance[end]);

}

}

测试数据：

6 8

0 4 30

0 2 10

0 5 100

1 2 5

2 3 50

4 5 60

4 3 20

3 5 10

0 3

输出：

路径为：0 3 4 路径长为50

Floyd算法求有权图最小路径

Floyd思路：floyd算法用的dp的思想，核心代码

for (int k = 0; k < vNum; k++) {

if(distance[i][j]>distance[i][k]+distance[k][j])

{

distance[i][j]=distance[i][k]+distance[k][j];

index=k;

}

}

求i到j的最短路径，通过遍历每一种情况，从i跳到k再有k跳到j，遍历每一个可能的k值，最后求得到最小路径。

import java.util.Scanner;

public class Floyd {

public static void main(String[] args) {

final int MAX=10000;

Scanner in=new Scanner(System.in);

int vNum=in.nextInt();

int edgeNum=in.nextInt();

//二维数值用来表示图

int distance[][]=new int[vNum][vNum];

int [][] path=new int [vNum][vNum];

//进行初始化，任意两个点的距离无限大

for (int i = 0; i

for (int j = 0; j < vNum; j++) {

distance[i][j]=MAX;

if(i==j)

distance[i][j]=0;

}

}

//读取数据，设置权值

for (int i = 0; i < edgeNum; i++) {

distance[in.nextInt()][in.nextInt()]=in.nextInt();

}

//起点

int v0=in.nextInt();

//结束点

int end=in.nextInt();

in.close();

for (int i = 0; i < vNum; i++) {

for (int j = 0; j

int index=i;

for (int k = 0; k < vNum; k++) {

if(distance[i][j]>distance[i][k]+distance[k][j])

{

distance[i][j]=distance[i][k]+distance[k][j];

index=k;

}

}

path[i][j]=index;

}

}

System.out.println("最短路径长为:"+distance[v0][end]);

System.out.print("路径为:"+end+" ");

while(true)

{

if(end==v0)

break;

System.out.print(path[v0][end]+" ");

end=path[v0][end];

}

}

}

测试数据：

6 8

0 4 30

0 2 10

0 5 100

1 2 5

2 3 50

4 5 60

4 3 20

3 5 10

0 3

输出：

最短路径长为:50

路径为:3 4 0

我觉得分享是一种精神，分享是我的乐趣所在，不是说我觉得我讲得一定是对的，我讲得可能很多是不对的，但是我希望我讲的东西是我人生的体验和思考，是给很多人反思，也许给你一秒钟、半秒钟，哪怕说一句话有点道理，引发自己内心的感触，这就是我最大的价值(这是我喜欢的一句话，也是我写博客的初衷)