Java无向无权图的最短路径怎么实现

这篇文章主要讲解了"Java无向无权图的最短路径怎么实现"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"Java无向无权图的最短路径怎么实现"吧！

1. Dijkstra（迪杰斯特拉 权值都是正的）
   是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止
   算法的输入是：
   有权（有向）图
   起点（源）
   所有边的权非负
   算法的输出是：
   起点（源）到其他各点的最短路径

2. Floyd（弗洛伊德 可以带负权值）
   是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)

3. 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<=n;i++){            int temp = Integer.MAX_VALUE;            int u = v;            for (int j =1; j<= n;j++){                if (!s[j] && dist[j] ();    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;iL=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
感谢各位的阅读，以上就是"Java无向无权图的最短路径怎么实现"的内容了，经过本文的学习后，相信大家对Java无向无权图的最短路径怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！