Java無向無權圖的最短路徑怎么實現

150次閱讀

共計 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 小編將為大家推送更多相關知識點的文章，歡迎關注！

正文完