Map Navigation System (Graph Algorithm)

1.实验目的

为了更好地理解图数据结构，例如最短路径算法和最小生成树算法。

2.实验代码思路及算法复杂度分析

Graph类：记录图的顶点，边等信息

//GraphNode
record GraphNode(int v, double weight) {
}
​
//Edge
record GraphEdge(int s, int d, double weight) {
}
​
public class Graph {
    protected static final int NODE_COUNT = 26;
    private final List<List<GraphNode>> adjacencyList = new ArrayList<>();
    private final double[][] adjacencyMatrix;
​
    public Graph() {
        for (int i = 0; i < NODE_COUNT; i++) {
            adjacencyList.addLast(new ArrayList<>());     //初始化邻接链表
        }
​
        adjacencyMatrix = new double[NODE_COUNT][NODE_COUNT];
        for (int i = 0; i < NODE_COUNT; i++) {
            Arrays.fill(adjacencyMatrix[i], Double.MAX_VALUE);
            adjacencyMatrix[i][i] = 0; // Distance to self is 0
        }
    }
​
    //添加边
    public void addEdge(int start, int end, double weight) {
        adjacencyList.get(start).add(new GraphNode(end, weight));
        adjacencyList.get(end).add(new GraphNode(start, weight));
        adjacencyMatrix[start][end] = weight;
        adjacencyMatrix[end][start] = weight;
    }
}

记录路径信息函数collectPaths： collectPaths 方法通过前驱节点信息递归地构建最短路径，在最坏情况下，可能需要遍历图中的大部分节点来构建完整路径，其时间复杂度取决于图的结构和最短路径的分布情况，其时间复杂度为 O(V)，因为最多也就是遍历所有节点一次来构建路径。

 //路径信息
    private void collectPaths(ArrayList<ArrayList<Integer>> record, int temp, int next, int x, Deque<Integer> stack, double weight, List<String> paths) {
        //向前寻找路径信息
        while (record.get(temp).getFirst() != x) {
            if (temp < 0 || temp >= NODE_COUNT) {
                return;
            }
            int m = record.get(temp).size();
            if (m > 1) { //如果在同一级中有多个节点，就复制相关信息进入递归
                for (int i = 1; i < m; i++) {
                    int v = record.get(temp).get(i);
                    Deque<Integer> newStack = new LinkedList<>(stack);
                    newStack.push(v);
                    collectPaths(record, v, v, x, newStack, weight + adjacencyMatrix[v][next], paths);
                }
            }
            int v = record.get(temp).getFirst();
            if (v < 0 || v >= NODE_COUNT) {
                break;
            }
            stack.push(v);
            temp = v;
            weight += adjacencyMatrix[temp][next];
            next = temp;
        }
        weight += adjacencyMatrix[x][next];
​
        StringBuilder path = new StringBuilder();
        path.append((char) (x + 'A'));
        while (!stack.isEmpty()) {
            int index = stack.pop();
            path.append("->").append((char) ('A' + index));
        }
        path.append("\n最短距离为 ").append(String.format("%.2f", weight)).append(" km.\n");
        paths.add(path.toString());
    }

(1) Given two locations, show the shortest path from one to the other on the map and its length.

功能一：采用Dijkstra与Bellman-Ford算法。

操作代码如下：

button1.setOnAction(event -> {
            outputArea.clear();
            outputArea.appendText("Operation 1:\n");
            String start = location1.getText();
            String end = location2.getText();
            if (start.length() == 1 && end.length() == 1 &&
                    (start.charAt(0) >= 'A' && start.charAt(0) <= 'Z') &&
                    (end.charAt(0) >= 'A' && end.charAt(0) <= 'Z')) {
                outputArea.appendText("Following is Dijkstra Alogorithm.\n");
                // 使用Dijkstra算法求两点间最短路径
                List<String> resultD = graph.findShortestPathDijkstra(start.charAt(0), end.charAt(0));
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < resultD.size() - 1; i++) {
                    s.append(resultD.get(i));
                }
                s.append(resultD.get(resultD.size() - 1));
                outputArea.appendText("从 " + start + " 到 " + end + " 路线: " + s.toString() + "\n");
                outputArea.appendText("\nFollowing is Bellman-Ford Alogorithm.\n");
                // 使用Bellman-Ford算法求两点间最短路径（作为另一种解法示例，可按需选用或扩展更多算法对比）
                List<String> resultBF = graph.findShortestPathBellmanFord(start.charAt(0), end.charAt(0));
                StringBuilder s2 = new StringBuilder();
                for (int i = 0; i < resultD.size() - 1; i++) {
                    s2.append(resultBF.get(i));
                }
                s2.append(resultBF.get(resultBF.size() - 1));
                outputArea.appendText("从 " + start + " 到 " + end + " 路线: " + s2.toString() + "\n");
            } else {
                outputArea.appendText("输入地点错误，请重新输入。\n");
            }
        });

Dijkstra算法：

  //Dijkstra算法 单源最短路径
    public List<String> findShortestPathDijkstra(char s, char d) {
        int start = s - 'A', end = d - 'A';
        double[] distance = new double[NODE_COUNT];  //距离
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();  //记录前一个节点
        for (int i = 0; i < NODE_COUNT; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(-1); // 初始化
            lists.add(list);
        }
        boolean[] visited = new boolean[NODE_COUNT];  //记录是否已经访问过了
​
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
​
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingDouble(a -> distance[a])); //最小堆
        heap.add(start);
​
        while (!heap.isEmpty()) {
            int index = heap.poll();
            if (visited[index]) continue;
            visited[index] = true;
            int l = adjacencyList.get(index).size();
            for (int i = 0; i < l; i++) {
                int ver = adjacencyList.get(index).get(i).v();      //提取相邻的节点信息
                double weight = adjacencyList.get(index).get(i).weight();
​
                if (visited[ver]) continue;
​
                if (distance[index] + weight < distance[ver]) {
                    distance[ver] = distance[index] + weight;
                    lists.remove(ver);
                    ArrayList<Integer> al = new ArrayList<>();
                    al.add(index);
                    lists.add(ver, al);
                    heap.add(ver);
                } else if (!visited[ver] && distance[index] + weight == distance[ver]) {
                    if (lists.get(ver).getFirst() == -1) {
                        lists.get(ver).removeFirst();
                        lists.get(ver).add(index);
                    } else {
                        lists.get(ver).add(index);
                    }
                }
            }
        }
        Deque<Integer> stack = new LinkedList<>();
        stack.add(end);
        List<String> paths = new ArrayList<>();
        collectPaths(lists, end, end, start, stack, 0, paths);
        return paths;
    }

时间复杂度分析：

1. 初始化：

   • 初始化 lists 用于记录前驱节点，时间复杂度为O(V)。

   • 初始化 visited ,d数组，时间复杂度为O(V)。

2. 优先队列的初始化：

   • 使用最小堆（即 PriorityQueue）来存储未访问的节点，初始时间复杂度为O(log⁡V)。

3. 主循环和更新：

   • 外层循环执行，直到 heap 为空。最坏情况下，如果图是稀疏的，Dijkstra 将会遍历所有的节点，即V次。

在每次迭代中，主要操作包括：

• 从 heap 中取出一个节点，时间复杂度为O(logV)。

• 更新相邻节点的距离：

  • 对每个相邻节点，检查是否被访问，如果没有，则更新距离和前驱节点，这个相邻节点的处理可能会遍历所有与该节点相邻的边。

假设 E 是图中的边数，对于每个节点，最坏情况下，可能会遍历所有边，时间复杂度在这一部分是O(E*logV)。

综上所述：

稀疏图(