• Dijkstra搜索简介


    概念

    Dijkstra算法是一种用于在加权图中找到最短路径的算法。它通过计算从起点到每个节点的最短路径来解决问题。Dijkstra算法适用于没有负权边的图。Dijkstra算法使用一个距离数组来记录从起点到每个节点的最短距离。它通过不断选择距离最短的节点来扩展搜索范围,直到找到目标节点或遍历完所有节点。

    Dijkstra算法用于解决从一个节点到其他所有节点的最短路径问题,例如在地图上找到从一个城市到其他城市的最短路径,或者在网络中找到从一个节点到其他节点的最短路径。

    算法特点

    • 使用一个距离数组来记录从起点到每个节点的最短距离。
    • 通过选择距离最短的节点来扩展搜索范围。
    • 可以通过优先队列来加速搜索过程,以便快速找到距离最短的节点。
    • 可以通过使用堆数据结构来实现优先队列,以提高算法的效率。

    优点

    • 能够找到从起点到每个节点的最短路径。
    • 对于没有负权边的图,Dijkstra算法是正确且有效的。

    缺点

    • 对于有负权边的图,Dijkstra算法无法正确处理。
    • 对于大规模图,Dijkstra算法的时间复杂度较高。

    适用场景

    • 寻找从一个节点到其他所有节点的最短路径。
    • 地图路径规划问题,如导航系统。
    • 网络路由问题。

    实现代码

    1. import java.util.*;
    2. class Node implements Comparable {
    3. int id;
    4. int distance;
    5. public Node(int id, int distance) {
    6. this.id = id;
    7. this.distance = distance;
    8. }
    9. @Override
    10. public int compareTo(Node other) {
    11. return Integer.compare(this.distance, other.distance);
    12. }
    13. }
    14. public class Dijkstra {
    15. private int[][] graph;
    16. private int numNodes;
    17. public Dijkstra(int[][] graph, int numNodes) {
    18. this.graph = graph;
    19. this.numNodes = numNodes;
    20. }
    21. public int[] findShortestPath(int start) {
    22. int[] distances = new int[numNodes];
    23. Arrays.fill(distances, Integer.MAX_VALUE);
    24. distances[start] = 0;
    25. PriorityQueue queue = new PriorityQueue<>();
    26. queue.offer(new Node(start, 0));
    27. while (!queue.isEmpty()) {
    28. Node current = queue.poll();
    29. for (int neighbor = 0; neighbor < numNodes; neighbor++) {
    30. if (graph[current.id][neighbor] != 0) {
    31. int distance = distances[current.id] + graph[current.id][neighbor];
    32. if (distance < distances[neighbor]) {
    33. distances[neighbor] = distance;
    34. queue.offer(new Node(neighbor, distance));
    35. }
    36. }
    37. }
    38. }
    39. return distances;
    40. }
    41. public static void main(String[] args) {
    42. int[][] graph = {
    43. {0, 4, 0, 0, 0, 0, 0, 8, 0},
    44. {4, 0, 8, 0, 0, 0, 0, 11, 0},
    45. {0, 8, 0, 7, 0, 4, 0, 0, 2},
    46. {0, 0, 7, 0, 9, 14, 0, 0, 0},
    47. {0, 0, 0, 9, 0, 10, 0, 0, 0},
    48. {0, 0, 4, 14, 10, 0, 2, 0, 0},
    49. {0, 0, 0, 0, 0, 2, 0, 1, 6},
    50. {8, 11, 0, 0, 0, 0, 1, 0, 7},
    51. {0, 0, 2, 0, 0, 0, 6, 7, 0}
    52. };
    53. int numNodes = graph.length;
    54. int start = 0;
    55. Dijkstra dijkstra = new Dijkstra(graph, numNodes);
    56. int[] distances = dijkstra.findShortestPath(start);
    57. for (int i = 0; i < numNodes; i++) {
    58. System.out.println("Distance from node " + start + " to node " + i + ": " + distances[i]);
    59. }
    60. }
    61. }

  • 相关阅读:
    微电子/集成电路专业学术期刊汇总!
    逃不过转行的命运,与互联网无缘了
    CentOS 7.9 环境下搭建k8s集群(一主两从)
    Centos7 编写开机监测gdm服务退出的脚本
    文心一言 Python编程之
    集群性能优化:压缩和扩容策略
    戏说领域驱动设计(十八)——内验
    记录:2022-9-25 IO概念 字符串的排列 路径总和 III BIO 线程池 IO概念(1)
    Spring MVC 启动流程?
    PIM—SM理论讲解
  • 原文地址:https://blog.csdn.net/aidscooler/article/details/133578352