Java 中的优美路径代码

2025年1月6日 | 3 分钟阅读

在图论中，优美路径（beautiful path）是指加权图中满足特定美学标准的一条路径，例如最小成本、最小距离，或符合颜色或边类型的特定约束。寻找优美路径可能是编程竞赛、路由算法和网络设计中的一个常见问题。

在本节中，我们将探讨使用Java在图中寻找优美路径的概念。

图的表示
Dijkstra算法用于计算最短路径

1. 图的表示

在Java中表示图，我们通常使用邻接表或邻接矩阵。为了提高效率，特别是对于稀疏图，我们将使用邻接表。

Graph.java

import java.util.*;
class Graph {
    private int vertices;
    private LinkedList<Edge>[] adjacencyList;
    class Edge {
        int target;
        int weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }
    void addEdge(int source, int target, int weight) {
        adjacencyList[source].add(new Edge(target, weight));
        adjacencyList[target].add(new Edge(source, weight)); // For undirected graph
    }
}

2. Dijkstra算法用于计算最短路径

Dijkstra算法是一种著名的算法，用于在具有非负权重的图中查找从源顶点到所有其他顶点的最短路径。

Dijkstra.java

class Dijkstra {
    static class Node implements Comparable<Node> {
        int vertex;
        int distance;
        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
    int[] dijkstra(Graph graph, int source) {
        int V = graph.adjacencyList.length;
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;
            for (Graph.Edge edge : graph.adjacencyList[u]) {
                int v = edge.target;
                int weight = edge.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }
}

3. 完整的Java代码示例

将所有内容组合起来，这是一个用于在图中查找最短优美路径的完整Java程序。

BeautifulPathDemo.java

import java.util.*;
class Graph {
    private int vertices;
    private LinkedList<Edge>[] adjacencyList;
    class Edge {
        int target;
        int weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }
    void addEdge(int source, int target, int weight) {
        adjacencyList[source].add(new Edge(target, weight));
        adjacencyList[target].add(new Edge(source, weight)); // For undirected graph
    }
    LinkedList<Edge>[] getAdjacencyList() {
        return adjacencyList;
    }
}
class BeautifulPath {
    static class Node implements Comparable<Node> {
        int vertex;
        int distance;
        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
    int[] beautifulPath(Graph graph, int source, int maxWeight) {
        int V = graph.getAdjacencyList().length;
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;
            for (Graph.Edge edge : graph.getAdjacencyList()[u]) {
                int v = edge.target;
                int weight = edge.weight;
                if (weight <= maxWeight && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }
}
public class BeautifulPathDemo {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 3);
        BeautifulPath bp = new BeautifulPath();
        int[] distances = bp.beautifulPath(graph, 0, 3);
        System.out.println("Distances from source 0:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Vertex " + i + " -> " + distances[i]);
        }
    }
}

输出

 
Distances from source 0:
Vertex 0 -> 0
Vertex 1 -> 4
Vertex 2 -> 3
Vertex 3 -> 6
Vertex 4 -> 8
Vertex 5 -> 11

结论

在本节中，我们探讨了使用Java在图中寻找优美路径的概念。我们从图的表示开始，然后是用于查找最短路径的Dijkstra算法。最后，我们提供了一个完整的Java示例来演示实现。

下一个主题Boolean-evaluation-in-java

Java 中的优美路径代码

1. 图的表示

2. Dijkstra算法用于计算最短路径

3. 完整的Java代码示例

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的优美路径代码

1. 图的表示

2. Dijkstra算法用于计算最短路径

3. 完整的Java代码示例

结论

相关帖子

Java 中的闰年程序

ImageIcon Class Java

Java 程序查找未排序数组中缺失的最小正数

Merge Two Sorted Linked Lists in Java

在 Java 中多次执行 main() 方法

HashSet 与 TreeSet

Real-Time Chat Application in Java

Java 程序将布尔值转换为整数

Trapping Rain Water Problem in Java

Array Rotation in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器