迪杰斯特拉算法
1.什么是迪杰斯特拉算法？
迪杰斯特拉算法是一种用于在加权图中找到最短路径的算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。这个算法可以解决单源最短路径问题，即从图中的一个顶点到其他所有顶点的最短路径问题。它是一个贪心算法，通过不断选择最小的未处理的顶点来更新其他顶点的最短路径。
- 迪杰斯特拉算法不适用于包含负权边的图
2.算法步骤
算法的基本步骤：
-
初始化：选择源点，并将所有顶点的最短路径估计值初始化为无穷大，除了源点自身初始化为0。
-
选择最小的未处理顶点：从未处理的顶点中选择一个距离最小的顶点。
-
更新邻接顶点的最短路径：对于刚刚选择的顶点，更新所有邻接顶点的最短路径估计值。
-
重复步骤2和3，直到所有顶点都被处理过。
实现思路：
首先设置一个Graph包含7个顶点的有向无权图，设置源点为0，计算从源点到剩余节点的最短路径。
引入两个集合dist和distset。dist的作用是记录已求出最短路径的顶点，而distset则是记录还未求出最短路径的顶点(以及该顶点到起点vs的距离)。
初始时，dist中只有起点vs；distset中是除vs之外的顶点，并且distset中顶点的路径是"起点vs到该顶点的路径"。然后，从distset中找出路径最短的顶点，并将其加入到dist中；接着，更新U中的顶点和顶点对应的路径。 然后，再从distset中找出路径最短的顶点，并将其加入到dist中；接着，更新distset中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。
3.代码实现
public class DijkstraAlgorithm {
// 定义无穷大，用于初始化距离
public static final int INF = Integer.MAX_VALUE;
// 迪杰斯特拉算法实现
public static void dijkstra(int[][] graph, int src) {
int[] dist = new int[graph.length]; // 存储源点到各点的最短距离
boolean[] sptSet = new boolean[graph.length]; // 标记节点是否处理过
// 初始化所有距离为无穷大，sptSet[]为false
for (int i = 0; i < graph.length; i++) {
dist[i] = INF;
sptSet[i] = false;
}
// 源点到自身的距离始终为0
dist[src] = 0;
// 找到所有顶点的最短路径
for (int count = 0; count < graph.length - 1; count++) {
// 选择一个最小距离的未处理节点
int u = minDistance(dist, sptSet);
// 标记节点为已处理
sptSet[u] = true;
// 更新相邻节点的距离
for (int v = 0; v < graph.length; v++) {
// 更新dist[v]只有在以下情况：
// 1. 节点v未被处理
// 2. 存在从u到v的边
// 3. 从src到v的总权重小于当前dist[v]的值
if (!sptSet[v] && graph[u][v] != 0 &&
dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 打印构建的距离数组
printSolution(dist);
}
// 辅助函数，找到最短距离中未处理的节点
public static int minDistance(int[] dist, boolean[] sptSet) {
int min = INF, minIndex = -1;
for (int v = 0; v < dist.length; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
// 打印最短距离数组
public static void printSolution(int[] dist) {
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < dist.length; i++) {
System.out.println(i + " \t\t " + dist[i]);
}
}
public static void main(String[] args) {
// 示例图的邻接矩阵表示
int[][] graph = new int[][]{
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0); // 以节点0为源点
}
}