今天把所有背景都换成了二次元高清大图。Dijkstra最短路径算法
题目:Dijkstra最短路径算法
设计人：张钦颖
学号：1414080901218
一、 实验环境：
1、硬件环境：个人机，CPU主频：4.01Ghz 内存：16G
2、软件环境：操作系统：win10
编程语言：C++
二、 实验任务解决方案：
1、 Dijkstra最短路径算法的流程图。
（1） 创建一组sptSet（最短路径数组），它存的是已经在SPT里的节点，也就是这些是已经计算过的，确定的最小值，一开始这里是空的。
（2） 给所有的给定图中的节点一个指定的距离值。将所有的距离值初始化为无限，将源节点初始为0。
（3） 当另一个（保存未放入SPT的节点的那个）不为空时：
① 选择一个不在SPTset中一个离源点距离最小的节点
② 把它加入SPTset
③ 更新所有于这个节点临近的节点的距离值。为了更距离值，遍历这个点所有的相邻点。对于每一个相邻的节点，如果这临近点u的距离值（从源节点开始的和）比v（新加入的）小，就把v的距离值更新
例如：
一开始SPTset是空的，并且它初始化的距离值是{0，INF，INF，INF，INF，INF，INF，INF}，其中INF表示无限。现在选择最小距离值的顶点。我们选了节点0，将它加入到sptSet。所以sptSet变为{0}。加入0至sptSet后，更新其相邻顶点的距离值。0相邻的节点为1和6，他们的距离值便被更新成3和4。图中标示出在SPT的顶点显示为绿色。
然后我们选择一个不包含在SPT里一个路径值为最小的一个节点，节点1被选了而且被加入到了sptSET，所以sptSET现在变为了{0,1}更新1临近节点的距离值，临近节点为2跟8，节点2跟8的距离值便变成了3+6=9、3+16=19。
像上面一样选一个，我们选了节点6，加入到sptSet，所以sptSet变成了{0,1,6}，更新节点6的临近节点的距离值，临近节点是5和7，更新后5：4+20=24，7：4+10=14.
然后我们再选一个2加入，sptSet又新来了一个数字2，2的临近节点3和8便更新为11和26.
一直重复这些事儿直到sptset包含所有的节点：
最后，我们终于得到了一棵完整的最短路径树
2、Dijkstra最短路径算法实现的关键代码。
#include <stdio.h>
#include <limits.h>
// Number of vertices in the graph
#define V 9
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] < min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[], int n)
{
printf("顶点\t\t距离源点的最短路径\n");
for (int i = 0; i < V; i++)
printf("%d \t\t%d\n", i, dist[i]);
}
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if distance to v is not in sptSet, there
// is an edge from u to v, and total weight of path from src to
// v through u is smaller than dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {
{ 0, 3, 0, 0, 0, 0, 4, 0, 0 },
{ 3, 0, 6, 0, 0, 0, 0, 0, 16 },
{ 0, 6, 0, 2, 0, 0, 0, 0, 17 },
{ 0, 0, 2, 0, 4, 0, 0, 0, 9 },
{ 0, 0, 0, 4, 0, 11, 0, 7, 0 },
{ 0, 0, 0, 0, 11, 0, 20, 0, 0 },
{ 4, 0, 0, 0, 0, 20, 0, 10, 0 },
{ 0, 0, 0, 0, 7, 0, 10, 0, 1 },
{ 0, 16, 17, 9, 0, 0, 0, 1, 0 }
};
dijkstra(graph, 0);
return 0;
}
三、 Dijkstra最短路径算法的计算复杂度分析（最好、最差、平均情况复杂度）：
（1） 最好的情况：每个顶点第一次检测到就是路径值就是最短路径。复杂度最低。
复杂度为：2n²+6n
（2） 最坏情况：顶点被检测了1次以上，并且每次检测都更新路径值为最小，即每次找的都不是最短路径，直到最后一次检测。复杂度最高
复杂度为：3n²+6n
（3） 平均情况复杂度：时间复杂度为O(n²)
四、 总结综合实验心得体会：
本次的Dijkstra最短路径算法在数据结构的课程上也接触过，所以感觉这个不成问题，选用的例子是自己随手画出来的，然后按照Dijkstra最短路径算法把流程步骤分别画了出来。然后其他部分参考了一下wiki以及geek论坛等国外大神的论文。还有很多东西老师在课堂上也给我们又讲了一遍，所以从算法思想上就不成多大问题了，主要是代码，而且必须得了解了算法才能mark得出代码来，否则根本无从下手。
头条