当前位置：首页 > news >正文

迪杰斯特拉

news 2025/5/21 8:45:06

BFS其实就是while循环里面套for循环。其中while循环控制一层一层往下走，for循环控制遍历每一层的节点。BFS算法处理的是无权图的搜索问题，所谓无权图，可以认为每条边的权重是1，从start起点到任意一个节点之间的路径权重就是它们之间“边”的条数。

743. 网络延迟时间 - 力扣（LeetCode）

最短路径

dj:不能处理负权图【O(V²)V是节点】

import java.util.*;// 节点类，表示图中的一个点（如房间门口、走廊交叉点）
class Node {private String id;  // 节点标识，如 "Room1Door"private double x, y;  // 节点在地图中的坐标public Node(String id, double x, double y) {this.id = id;this.x = x;this.y = y;}public String getId() {return id;}public double getX() {return x;}public double getY() {return y;}// 计算两个节点之间的欧几里得距离public double distanceTo(Node other) {double dx = this.x - other.x;double dy = this.y - other.y;return Math.sqrt(dx * dx + dy * dy);}@Overridepublic String toString() {return id;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Node node = (Node) o;return id.equals(node.id);}@Overridepublic int hashCode() {return id.hashCode();}
}// 边类，表示两个节点之间的连接
class Edge {private Node destination;  // 边的终点private double weight;     // 边的权重（如距离）public Edge(Node destination, double weight) {this.destination = destination;this.weight = weight;}public Node getDestination() {return destination;}public double getWeight() {return weight;}
}// 图类，使用邻接表表示
class Graph {private Map<Node, List<Edge>> adjacencyList;public Graph() {this.adjacencyList = new HashMap<>();}// 添加节点public void addNode(Node node) {adjacencyList.putIfAbsent(node, new ArrayList<>());}// 添加边（无向边）public void addEdge(Node source, Node destination, double weight) {addNode(source);addNode(destination);// 添加双向边adjacencyList.get(source).add(new Edge(destination, weight));adjacencyList.get(destination).add(new Edge(source, weight));}// 获取节点的邻接表public List<Edge> getNeighbors(Node node) {return adjacencyList.getOrDefault(node, Collections.emptyList());}// 获取所有节点public Set<Node> getNodes() {return adjacencyList.keySet();}
}// Dijkstra算法实现（使用邻接表，不使用优先级队列）
class Dijkstra {private Graph graph;public Dijkstra(Graph graph) {this.graph = graph;}// 计算从起点到所有其他节点的最短路径public Map<Node, Double> computeShortestPaths(Node start) {Map<Node, Double> distance = new HashMap<>();  // 存储最短距离Map<Node, Boolean> visited = new HashMap<>();  // 存储节点是否已访问// 初始化for (Node node : graph.getNodes()) {distance.put(node, Double.MAX_VALUE);visited.put(node, false);}distance.put(start, 0.0);  // 起点到自身的距离为0// 遍历所有节点for (int i = 0; i < graph.getNodes().size() - 1; i++) {// 找到未访问节点中距离最小的节点Node minNode = null;double minDistance = Double.MAX_VALUE;for (Node node : graph.getNodes()) {if (!visited.get(node) && distance.get(node) < minDistance) {minDistance = distance.get(node);minNode = node;}}// 如果没有找到可处理的节点，退出循环if (minNode == null) break;// 标记当前节点为已访问visited.put(minNode, true);// 更新邻接节点的距离for (Edge edge : graph.getNeighbors(minNode)) {Node neighbor = edge.getDestination();double weight = edge.getWeight();if (!visited.get(neighbor) && distance.get(minNode) + weight < distance.get(neighbor)) {distance.put(neighbor, distance.get(minNode) + weight);}}}return distance;}// 计算从起点到终点的最短路径，并返回路径节点列表public List<Node> getPath(Node start, Node end) {Map<Node, Double> distance = new HashMap<>();Map<Node, Node> previous = new HashMap<>();Map<Node, Boolean> visited = new HashMap<>();// 初始化for (Node node : graph.getNodes()) {distance.put(node, Double.MAX_VALUE);previous.put(node, null);visited.put(node, false);}distance.put(start, 0.0);// 遍历所有节点for (int i = 0; i < graph.getNodes().size() - 1; i++) {// 找到未访问节点中距离最小的节点Node minNode = null;double minDistance = Double.MAX_VALUE;for (Node node : graph.getNodes()) {if (!visited.get(node) && distance.get(node) < minDistance) {minDistance = distance.get(node);minNode = node;}}if (minNode == null) break;visited.put(minNode, true);// 如果已经到达终点，提前结束if (minNode.equals(end)) break;// 更新邻接节点的距离for (Edge edge : graph.getNeighbors(minNode)) {Node neighbor = edge.getDestination();double weight = edge.getWeight();if (!visited.get(neighbor) && distance.get(minNode) + weight < distance.get(neighbor)) {distance.put(neighbor, distance.get(minNode) + weight);previous.put(neighbor, minNode);}}}// 构建路径LinkedList<Node> path = new LinkedList<>();Node current = end;while (current != null) {path.addFirst(current);current = previous.get(current);}// 如果路径的第一个节点不是起点，说明没有有效路径if (path.isEmpty() || !path.getFirst().equals(start)) {return Collections.emptyList();}return path;}
}// 示例：室内导航应用
public class IndoorNavigation {public static void main(String[] args) {// 创建图Graph graph = new Graph();// 添加节点（房间门口和走廊交叉点）Node room1Door = new Node("Room1Door", 0, 0);Node room2Door = new Node("Room2Door", 0, 10);Node corridor1 = new Node("Corridor1", 5, 5);Node corridor2 = new Node("Corridor2", 10, 5);Node room3Door = new Node("Room3Door", 15, 0);Node room4Door = new Node("Room4Door", 15, 10);// 添加边（使用节点间的实际距离）graph.addEdge(room1Door, corridor1, room1Door.distanceTo(corridor1));graph.addEdge(room2Door, corridor1, room2Door.distanceTo(corridor1));graph.addEdge(corridor1, corridor2, corridor1.distanceTo(corridor2));graph.addEdge(corridor2, room3Door, corridor2.distanceTo(room3Door));graph.addEdge(corridor2, room4Door, corridor2.distanceTo(room4Door));// 创建Dijkstra算法实例Dijkstra dijkstra = new Dijkstra(graph);// 计算从Room1Door到Room4Door的最短路径List<Node> path = dijkstra.getPath(room1Door, room4Door);// 输出路径System.out.println("从 " + room1Door + " 到 " + room4Door + " 的最短路径:");for (Node node : path) {System.out.println("- " + node);}}
}

为什么不能处理负权图：【贪心】

每次从未确定最短路径的节点中选择距离起点最小的节点,已访问的点距离不会更新