算法-数据结构（图）-迪杰斯特拉最短逻辑算法（ Dijkstra）

迪杰斯特拉算法（Dijkstra's Algorithm） 是一种用于计算单源最短路径的经典算法，由荷兰计算机科学家 艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra） 于1956年提出。它的主要目标是找到从图中的某个源节点到所有其他节点的最短路径。该算法适用于带权有向图或无向图，且要求边的权重非负。

---

核心思想

迪杰斯特拉算法采用贪心策略，通过逐步扩展已知的最短路径集合来求解问题。具体步骤如下：

1. 初始化：

   • 设置一个数组 dist[]，用于存储从源节点到每个节点的最短距离。初始时，源节点的距离为 0，其他节点的距离为 ∞（表示不可达）。

   • 设置一个数组 visited[]，用于标记节点是否已被访问（即是否已找到从源节点到该节点的最短路径）。

   • 设置一个数组 prev[]，用于记录每个节点的前驱节点，以便后续重建路径。

2. 选择当前最短路径节点：

   • 从未访问的节点中选择一个距离源节点最近的节点 u（即 dist[u] 最小）。

3. 更新邻居节点的距离：

   • 对于节点 u 的每个邻居节点 v，检查是否存在一条从源节点经过 u 到 v 的路径，且该路径的距离比当前已知的 dist[v] 更短。

   • 如果存在，则更新 dist[v] 为 dist[u] + weight(u, v)，并记录 v 的前驱节点为 u。

4. 标记节点为已访问：

   • 将节点 u 标记为已访问。

5. 重复：

   • 重复步骤 2~4，直到所有节点都被访问。

---

算法特点

1. 适用范围：

   • 适用于带权图，且边的权重必须非负。

   • 如果图中存在负权边，迪杰斯特拉算法可能会失效，此时可以使用 Bellman-Ford 算法。

2. 时间复杂度：

   • 使用**优先队列（堆）**优化后，时间复杂度为 O((V + E) log V)，其中 V 是节点数，E 是边数。

   • 如果使用简单的数组实现，时间复杂度为 O(V²)。

3. 空间复杂度：

   • 需要额外的空间存储 dist[]、visited[] 和 prev[]，空间复杂度为 O(V)。

算法实现示例

图数据定义

import java.util.ArrayList;
import java.util.List;//邻接矩阵表示图
public class YuGraph {//顶点List<Character> vList;//边的联通性，初始为0，不联通int [][] vG;//初始化YuGraph(List<Character> list){vList=list;vG=new int[list.size()][list.size()];for(int i=0;i<list.size();i++){for(int j=0;j<list.size();j++){vG[i][j]=Integer.MAX_VALUE;}}}//插入边public void insertVg(int i,int j,int val){vG[i][j]=val;}
}

插入的图

算法实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;//
public class Dijkstra {//1.迪杰斯特拉算法public static void Dijks(YuGraph yuGraph,int source){//顶点数量int n=yuGraph.vG.length;
//        System.out.println(n);//初始化最短距离int [] dist=new int[n];//初始设置为无限制大Arrays.fill(dist,Integer.MAX_VALUE);//目标点设置为0dist[source]=0;//访问数组标志,默认falseboolean [] flagArr=new boolean[n];//邻接矩阵int [][] vG=yuGraph.vG;//默认前驱节点int[] qianQU=new int [n];Arrays.fill(qianQU,-1);//遍历所有顶点找距离最小的索引开始更新邻居距离for(int i=0;i<n-1;i++){//开始访问的点int u=findMinIndex(dist,flagArr);
//            System.out.println(u);flagArr[u]=true;//开始访问它的邻居for(int v=0;v<n;v++){//没有被访问过,和上一个节点联通，且上一个节点有最短路径，并且新的路径比原来的还要小就更新if(!flagArr[v]&&vG[u][v]!=Integer.MAX_VALUE&&dist[u]!=Integer.MAX_VALUE&&dist[u]+vG[u][v]<dist[v]){//更新最短距离dist[v]= dist[u]+vG[u][v];//记录前驱qianQU[v]=u;}}}printResult(dist,qianQU);}//2.未访问，最短路径的点的序列public static int findMinIndex(int [] dist,boolean [] flagArr){int minIndex=-1;int minDis=Integer.MAX_VALUE;for(int i=0;i<dist.length;i++){if(flagArr[i]==false&&dist[i]<minDis){minIndex=i;minDis=dist[i];}}return minIndex;}//3.打印最短路径信息public static void printResult(int [] dist, int[] qianQU) {for (int i = 0; i < dist.length; i++) {System.out.print((char) ('A' + i));System.out.print(" 最短路径为: ");System.out.print(dist[i]);System.out.print(" 路径: ");printPath(qianQU, i);System.out.println();}}// 辅助方法：打印从源节点到目标节点的路径public static void printPath(int[] qianQU, int target) {if (qianQU[target] != -1) {printPath(qianQU, qianQU[target]);}System.out.print((char) ('A' + target) + " ");}public static void main(String[] args) {List<Character> list=new ArrayList<>();for(int i=0;i<5;i++){list.add((char)('A'+i));}YuGraph yuGraph=new YuGraph(list);//初始化图//ab 10 ac 2yuGraph.insertVg(0,1,10);yuGraph.insertVg(0,2,2);//bd 2yuGraph.insertVg(1,3,2);//cb5,cd2,ce10yuGraph.insertVg(2,1,5);yuGraph.insertVg(2,3,2);yuGraph.insertVg(2,4,10);//de 5yuGraph.insertVg(3,4,5);//调用迪杰斯特拉最短路径算法Dijks(yuGraph,0);}
}