最短路徑java

在Java中，最短路徑問題可以通過多種算法來解決，例如Dijkstra算法、A*算法、Bellman-Ford算法等。這裡我將提供一個簡單的Dijkstra算法的Java實現，用於找到圖中兩點之間的最短路徑。

首先，我們需要一個圖的數據結構來存儲圖的信息。這裡我們使用一個簡單的二維數組來表示圖，其中每個元素的值表示兩個頂點之間的權重。以下是一個簡單的圖的例子：

int[][] graph = {
    {0, 4, 8, 11},
    {4, 0, 7, 2},
    {8, 7, 0, 9},
    {11, 2, 9, 0}
};

這個圖表示四個頂點（0, 1, 2, 3）之間的權重。例如，從頂點0到頂點1的權重是4，從頂點0到頂點2的權重是8，等等。

現在，我們可以實現Dijkstra算法來找到從某個起始頂點到其他所有頂點的最短路徑。以下是一個簡單的Dijkstra算法的實現：

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 8, 11},
            {4, 0, 7, 2},
            {8, 7, 0, 9},
            {11, 2, 9, 0}
        };

        int source = 0; // 起始頂點
        int[] distances = dijkstra(graph, source);

        System.out.println("Distance from source to each vertex:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Vertex " + i + ": " + distances[i]);
        }
    }

    public static int[] dijkstra(int[][] graph, int source) {
        int vertices = graph.length;

        // 距離數組，存儲從起始頂點到每個頂點的最短路徑的距離
        int[] distances = new int[vertices];

        // 標記數組，表示頂點是否已被訪問過
        boolean[] visited = new boolean[vertices];

        // 初始化距離數組
        for (int i = 0; i < vertices; i++) {
            distances[i] = Integer.MAX_VALUE;
        }

        // 起始頂點的距離為0
        distances[source] = 0;

        // 優先佇列，用於存儲未訪問的頂點及其距離
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(distances::length));
        queue.offer(source);

        while (!queue.isEmpty()) {
            // 取出距離最短的頂點
            int vertex = queue.poll();

            // 已經訪問過該頂點，跳過
            if (visited[vertex]) {
                continue;
            }

            // 訪問該頂點
            visited[vertex] = true;

            // 遍歷該頂點的鄰居頂點
            for (int i = 0; i < vertices; i++) {
                // 如果存在權重為0的邊，則表示是障礙物，不考慮
                if (graph[vertex][i] == 0) {
                    continue;
                }

                // 更新鄰居頂點的距離
                int newDist = distances[vertex] + graph[vertex][i];
                if (newDist < distances[i]) {
                    distances[i] = newDist;
                    queue.offer(i);
                }
            }
        }

        return distances;
    }
}

在這個實現中，我們使用了一個優先佇列來存儲未訪問的頂點及其距離。每次我們從佇列中取出距離最短的頂點，並檢查其鄰居頂點，如果存在更短的路徑，則更新距離。

請注意，這個實現假設圖是無向的（即權重是對稱的），並且沒有負權重邊。如果圖是有向的或有負權重邊，你需要對算法進行相應的修改。

此外，這個實現只找到了從起始頂點到每個其他頂點的最短路徑，而不是兩點之間的最短路徑。如果你需要找到兩點之間的最短路徑，你需要在找到所有頂點的距離後，使用BFS或DFS來找到實際的路徑。