溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Java無向無權圖的最短路徑怎么實現(xiàn)”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java無向無權圖的最短路徑怎么實現(xiàn)”吧！
Dijkstra（迪杰斯特拉 權值都是正的）
是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止
算法的輸入是：
有權（有向）圖
起點（源）
所有邊的權非負
算法的輸出是：
起點（源）到其他各點的最短路徑
Floyd（弗洛伊德 可以帶負權值）
是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)
Bellman-Ford（伯爾曼 單源最短路徑可以帶負權值,比Dijkstra要廣）
首先假設源點到所有點的距離為無窮大，然后從任一頂點u出發(fā)，遍歷其它所有頂點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<=n;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<n;i++)
for(int j=0;j<n;j++){
path[i][j]=-1; //初始化當前的路徑長度表
dist[i][j]=Arcs[i][j]; //初始化當前的路徑表
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;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<25; 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<25; 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<5; 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無向無權圖的最短路徑怎么實現(xiàn)”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Java無向無權圖的最短路徑怎么實現(xiàn)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
