在本教程中，我们将学习Dijkstra的算法。它用于获取单源最短路径算法。
那么，单一来源最短路径是什么？
系统会为您提供加权图，并为您提供源。您需要找到从源顶点到图中所有其他顶点的最短路径。
例：
因此，要找到“ A”和“ C”之间的最短路径，可以通过以下方式从“ A”到达“ C”：
一种 -> E -> C = 4 + 3 = 7
一种 -> B -> C = 2 + 4 = 6
一种 -> D -> E -> C = 5 + 2 + 3 = 9
因此，最短路径是A-> B -> C.
因此，要解决此问题，我们可以生成从源顶点到其他每个顶点的所有可能路径。找到所有路径的权重，比较这些权重并找到所有这些权重的最小值。可以使用Dijkstra的算法对其进行优化。
Dijkstra的算法是贪婪算法。该图应具有以下属性才能工作：
- 该算法适用于有向图和无向图。
- 所有边缘应具有正重量。
- 图应已连接。
以下是执行Dijkstra算法的步骤。
步骤1：选择任意一个顶点作为起始顶点。
步骤2：将所有其他顶点的距离设为INF
第3步：从起始顶点访问其所有相邻/相邻顶点，并写下其成本/价值。
步骤4：现在我们已经完成了对所有相邻顶点的访问，我们将源顶点设置为已访问。
步骤5：选择另一个顶点，使得距源顶点的距离最小。
第6步：现在，记下到达起始国彩网的相邻国彩网所需的成本，以使距离应最小。
步骤7：重复直到访问完所有国彩网。
选择从源顶点到目标顶点的新路径的长度的过程小于当前值，然后以最短的值进行更新。此过程称为放松。
放松的过程可以在下面找到：
考虑下图：
现在，从“ a”到“ b”的成本是多少？是5
但是有一条从“ a”到“ b”的路径，成本更低。
即“ a”-> “c” -> “b”. the cost is 3.
因此，我们将使用从“ a”到“ b”到“ c”的路径。因为成本较低。这称为放松。
现在，借助示例来了解该算法。
考虑下图：
我们将选择国彩网“ a”作为起始国彩网，使国彩网“ a”到所有其他国彩网的所有国彩网为无穷大，并且从“ a”到“ a”的距离为零。
从国彩网“ a”检查相邻的国彩网，即“ b”和“ c”，记下成本，以代替Infinity，因为越少越好。
现在，使国彩网“ a”成为已访问国彩网，因为它访问了所有相邻国彩网。
现在，检查成本较低的国彩网。
国彩网“ b”成本形式“ a”为2。
来自“ a”的国彩网“ c”成本为3。
因此，我们将选择国彩网“ b”。
现在我们将放松与国彩网“ b”相邻的所有国彩网。仅国彩网“ d”与国彩网“ b”相邻。因此，从“ a”到“ d”的总成本为
- 一种 -> b + b -> d
- 2 + 4 = 6
由于6小于INF，因此更新成本并使国彩网“ b”成为已访问国彩网。
现在我们选择国彩网“ c”，因为与国彩网“ d”相比，成本更低。
现在尝试放松与国彩网“ c”相邻的所有国彩网。国彩网“ d”和国彩网“ e”相邻。
因此，国彩网“ d”的总成本为：
- 一种 -> c + c-> d
- 3 + 1
- 4
国彩网“ e”的总成本为：
- a->c + c->e
- 3+8
- 11
现在，将国彩网“ c”设置为已访问。
现在我们选择国彩网“ d”，因为成本低于其他两个国彩网。
现在放宽与国彩网d相邻的所有边。
国彩网“ c”和国彩网“ f”相邻。
现在，国彩网“ c”的总成本为：
- 国彩网“ d”的成本+“ d”到“ c”的成本。
- 4 + 1
- 5
“ 5”越大，“ 3”越大。不要更新值。
国彩网“ f”的总成本：
- 国彩网“ d”的成本+“ d”至“ f”的成本
- 4 + 9
- 13
13小于INF。因此，更新并将其标记为已访问。
现在，国彩网“ e”和国彩网“ f”的成本相同。选择任何国彩网。
我们将选择国彩网“ e”。
国彩网“ e”和国彩网“ f”相邻。
因此，国彩网“ c”的总成本为：
- 国彩网“ e”的成本+ e的成本-> c
- 11 + 8
- 19 > 3
- 因此，请不要更新。
国彩网“ f”的总成本：
- 国彩网“ e”的成本+ e的成本-> f
- 11 + 2
- 13
- 因此，请不要更新。
使“ e”为已访问。因此解决方案
通过以上步骤，我们可以使用以下公式来计算国彩网的代码。
将“ u”视为源顶点。
“ v”作为目标顶点。
Then if (distance(u) + cost of path (u, v) < distance_at (v)) then distance(v) = distance_at(u) + cost of path (u, v)
从上图可以看到，Dijkstra的算法用于查找从源国彩网到所有其他国彩网的最短路径，而不仅仅是目标国彩网。
Dijkstra算法在C ++中的实现
#include <iostream>
#include <climits>
using namespace std;
const int numberVertex = 10;
int minDistance(int distance[], bool ShortestPathTree[])
{
int min = INT_MAX, min_index;
for(int vertex = 0; vertex < numberVertex; vertex++)
{
if(ShortestPathTree[vertex] == false && distance[vertex] <= min)
{
min = distance[vertex];
min_index = vertex;
}
}
return min_index;
}
void dijkstra(int graph[numberVertex][numberVertex], int source)
{
int distance[numberVertex];
bool ShortestPathTree[numberVertex];
for(int i = 0; i < numberVertex; i++)
{
distance[i] = INT_MAX;
ShortestPathTree[i] = false;
}
distance[source] = 0;
for(int count = 0; count < numberVertex - 1; count++)
{
int u = minDistance(distance, ShortestPathTree);
ShortestPathTree[u] = true;
for(int vertex = 0; vertex < numberVertex; vertex++)
if(ShortestPathTree[vertex] == 0 && graph[u][vertex] != 0 &&
distance[u] != INT_MAX && distance[u] + graph[u][vertex] < distance[vertex])
distance[vertex] = distance[u] + graph[u][vertex];
}
cout << "Distance from Source:" << endl;
cout << "Vertex\t\tDistance" << endl;
for(int i = 0; i < numberVertex; i++)
cout << i << "\t\t" << distance[i] << endl;
}
int main()
{
int graph[numberVertex][numberVertex] = {{0, 14, 0, 7, 0, 0, 0, 8, 0, 10},
{14, 0, 8, 0, 0, 0, 0, 11, 0, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2, 0},
{7, 0, 7, 0, 9, 12, 0, 0, 0, 5},
{0, 0, 0, 9, 0, 0, 0, 0, 0, 0},
{0, 0, 4, 0, 0, 0, 2, 0, 0, 11},
{0, 0, 0, 12, 0, 2, 0, 1, 6, 15},
{8, 11, 0, 0, 0, 0, 1, 0, 7, 0},
{0, 0, 2, 0, 0, 0, 6, 7, 0, 0},
{10, 0, 0, 5, 0, 11, 15, 0, 0, 0}};
dijkstra(graph, 0);
return 0;
}
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
