单源最短路径算法java

单源最短路径算法是指在一个加权有向图中，从给定源点到所有其他点的最短路径问题。Java中可以使用Dijkstra算法实现单源最短路径。该算法的思路是从源点开始，每次选择当前距离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其他所有点的最短路径。具体实现可以参考引用中的代码实现部分和引用中的算法思路和正确性分析部分。

相关问题

单源最短路径贪心算法java

单源最短路径问题可以使用Dijkstra算法或Bellman-Ford算法来解决。其中Dijkstra算法是基于贪心策略的算法，可以用Java实现。以下是一个简单的Dijkstra算法实现示例：

import java.util.*;

public class DijkstraAlgorithm {
    private static final int MAX = 10001; // 无穷大，即表示不连通
    private static int[][] graph = new int[MAX][MAX];
    private static int[] dis = new int[MAX];
    private static boolean[] vis = new boolean[MAX];
    private static int n, start;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        int m = input.nextInt();
        start = input.nextInt();

        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    graph[i][j] = 0; // 自身到自身的距离为0
                } else {
                    graph[i][j] = MAX; // 其他的距离初始化为无穷大
                }
            }
        }

        // 读入边的权值
        for (int i = 1; i <= m; i++) {
            int u = input.nextInt();
            int v = input.nextInt();
            int w = input.nextInt();
            graph[u][v] = w;
        }

        // 初始化dis数组，表示起点到各点的距离
        for (int i = 1; i <= n; i++) {
            dis[i] = graph[start][i];
        }

        // Dijkstra算法主体部分
        vis[start] = true;
        for (int i = 1; i <= n; i++) {
            int min = MAX, u = start;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dis[j] < min) {
                    min = dis[j];
                    u = j;
                }
            }
            vis[u] = true;
            for (int v = 1; v <= n; v++) {
                if (!vis[v] && graph[u][v] < MAX) {
                    dis[v] = Math.min(dis[v], dis[u] + graph[u][v]);
                }
            }
        }

        // 输出起点到各点的最短距离
        for (int i = 1; i <= n; i++) {
            System.out.print(dis[i] + " ");
        }
    }
}

在上述代码中，我们使用邻接矩阵来表示图，其中graph[i][j]表示点i到点j的距离，如果无法到达，则距离为无穷大。dis数组表示起点到各点的最短距离，vis数组表示该点是否已被访问过。在Dijkstra算法主体部分中，我们先找出未被访问过的距离起点最近的点，然后更新其它点到起点的距离。最终输出起点到各点的最短距离。

单源最短路径贪心算法Java

单源最短路径贪心算法有多种实现方式，其中比较常见的是Dijkstra算法和Bellman-Ford算法。下面是Dijkstra算法的Java实现：

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        int n = 5; // 图中节点数
        int[][] graph = new int[][]{
                {0, 10, Integer.MAX_VALUE, 30, 100},
                {Integer.MAX_VALUE, 0, 50, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 60},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        }; // 图的邻接矩阵表示

        int[] dist = dijkstra(graph, n, 0); // 求从节点0出发到其他节点的最短距离
        System.out.println(Arrays.toString(dist)); // 输出结果
    }

    public static int[] dijkstra(int[][] graph, int n, int start) {
        int[] dist = new int[n]; // 存储从起点到各个节点的最短距离
        boolean[] visited = new boolean[n]; // 标记节点是否已经被访问过

        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为无穷大
        dist[start] = 0; // 起点到自身的距离为0

        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }

            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != Integer.MAX_VALUE) {
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
                }
            }
        }

        return dist;
    }
}