共计 5217 个字符，预计需要花费 14 分钟才能阅读完成。
这篇文章主要讲解了“Java 无向无权图的最短路径怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“Java 无向无权图的最短路径怎么实现”吧！
Dijkstra（迪杰斯特拉 权值都是正的）
是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止
算法的输入是：
有权（有向）图
起点（源）
所有边的权非负
算法的输出是：
起点（源）到其他各点的最短路径
Floyd（弗洛伊德 可以带负权值）
是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall 算法的时间复杂度为 O(N3)，空间复杂度为 O(N2)
Bellman-Ford（伯尔曼 单源最短路径可以带负权值, 比 Dijkstra 要广）
首先假设源点到所有点的距离为无穷大，然后从任一顶点 u 出发，遍历其它所有顶点 vi，计算从源点到其它顶点 vi 的距离与从 vi 到 u 的距离的和，如果比原来距离小，则更新，遍历完所有的顶点为止，即可求得源点到所有顶点的最短距离。
4. 无向无权图的最短路径算法
public class Dijkstra {
static int max = Integer.MAX_VALUE;
static int dist[] = new int[6];
static int prev[] = new int[6];
static int a[][] = { {0,max,10,max,30,100},
{max,0,5,max,max,max},
{max,max,0,50,max,max},
{max,max,max,0,max,10},
{max,max,max,20,0,60},
{max,max,max,max,max,0}
};
void dijkstra(int v,int a[][], int dist[], int prev[]){
int n = dist.length - 1;
boolean s[] = new boolean[n+1];
for (int i = 1; i = n;i++){ dist[i] = a[v][i];
s[i] = false;
if (dist[i] Integer.MAX_VALUE)
prev[i] = v;
else
prev[i] = -1;
}
dist[v] = 0;
s[v] = true;
for (int i=1;i i++){
int temp = Integer.MAX_VALUE;
int u = v;
for (int j =1; j = n;j++){ if (!s[j] dist[j] temp){
u = j;
temp = dist[j];
}
}
s[u] = true;
for (int j = 0;j = n; j++){ if(!s[j] a[u][j] Integer.MAX_VALUE){ int newDist = dist[u] + a[u][j];
if (newDist dist[j]){ dist[j] = newDist;
prev[j] = u;
}
}
}
}
}
void outPath(int m, int p[],int []d){ for (int i = 0; i dist.length; i++){ if (d[i] Integer.MAX_VALUE i != m){
System.out.print( v +i+ --
int next = p[i];
while (next != m){
System.out.print( v +next+ --
next = p[next];
}
System.out.println(v +m+ : +d[i]);
} else if( i != m)
System.out.println( v +i+ -- + v +m+ :no path
}
}
public static void main(String[] args) { Dijkstra d = new Dijkstra();
d.dijkstra(0,a,dist,prev);
d.outPath(0,prev,dist);
}
===================
import java.util.ArrayList;
public class Floyd {
/*
* 给出一个含有 n 个顶点的带权有向图，要求其每一对顶点之间的最短路径。 * 这里采用佛洛依德 (Floyd) 最短路径算法： */
private static int max=Integer.MAX_VALUE;
private static int [][]dist=new int[6][6]; // 存储最短路径
private static int [][]path=new int[6][6]; // 存储最短路径的长度
private static ArrayList list=new ArrayList Integer
private static int [][]Arcs={ {max,max,10,max,30,100},
{max,max,5,max,max,max},
{max,max,max,50,max,max},
{max,max,max,max,20,10},
{max,max,max,max,max,60},
{max,max,max,max,max,max}
};
public void findCheapestPath(int begin,int end,int Arcs[][]){ floyd(Arcs);
list.clear();
list.add(begin);
findPath(begin,end);
list.add(end);
}
public void findPath(int i,int j){ int k=path[i][j];
if(k==-1)
return ;
findPath(i,k);
list.add(k);
findPath(k,j);
}
public void floyd(int [][] Arcs){
int n=Arcs.length;
for(int i=0;i i++)
for(int j=0;j j++){ path[i][j]=-1; // 初始化当前的路径长度表
dist[i][j]=Arcs[i][j]; // 初始化当前的路径表
}
for(int k=0;k k++)
for(int i=0;i i++)
for(int j=0;j j++){ if(dist[i][k]!=max dist[k][j]!=max dist[i][k]+dist[k][j] dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Floyd f=new Floyd();
for(int i=0;i Arcs.length;i++)
for(int j=0;j Arcs.length;j++){ f.findCheapestPath(i, j, Arcs);
ArrayList Integer L=f.list;
System.out.print(i+ -- +j+ :
if(f.dist[i][j]==max){
System.out.println( 之间没有最短路径
System.out.println();
}
else{
System.out.println( 的最短路径是： System.out.print(L.toString()+
System.out.println(路径长度: +f.dist[i][j]);
System.out.println();
}
}
}
=============
import java.io.*;
import java.util.*;
public class bellmanford {
final public static int MAX = 1000000000;
// Short driver program to test the Bellman Ford s method.
public static void main(String[] args) {
// Read in graph.
int[][] adj = new int[5][5];
Scanner fin = new Scanner(System.in);
int numEdges = 0;
for (int i = 0; i i++) {adj[i/5][i%5] = fin.nextInt();
if (adj[i/5][i%5] != 0) numEdges++;
// Form edge list.
edge[] eList = new edge[numEdges];
int eCnt = 0;
for (int i = 0; i i++)
if (adj[i/5][i%5] != 0)
eList[eCnt++] = new edge(i/5, i%5, adj[i/5][i%5]);
// Run algorithm and print out shortest distances.
int[] answers = bellmanford(eList, 5, 0);
for (int i=0; i i++)
System.out.print(answers[i]+
System.out.println();
// Returns the shortest paths from vertex source to the rest of the
// vertices in the graph via Bellman Ford s algorithm.
public static int[] bellmanford(edge[] eList, int numVertices, int source) {
// This array will store our estimates of shortest distances.
int[] estimates = new int[numVertices];
// Set these to a very large number, larger than any path in our
// graph could possibly be.
for (int i=0; i estimates.length; i++)
estimates[i] = MAX;
// We are already at our source vertex.
estimates[source] = 0;
// Runs v-1 times since the max number of edges on any shortest path is v-1, if
// there are no negative weight cycles.
for (int i=0; i numVertices-1; i++) {
// Update all estimates based on this particular edge only.
for (edge e: eList) {if (estimates[e.v1]+e.w estimates[e.v2])
estimates[e.v2] = estimates[e.v1] + e.w;
return estimates;
class edge {
public int v1;
public int v2;
public int w;
public edge(int a, int b, int c) {
v1 = a;
v2 = b;
w = c;
public void negate() {w = -w;}感谢各位的阅读，以上就是“Java 无向无权图的最短路径怎么实现”的内容了，经过本文的学习后，相信大家对 Java 无向无权图的最短路径怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！
正文完
