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的距离值更新

例如:

gaitubao_1.jpg


        一开始SPTset是空的,并且它初始化的距离值是{0,INF,INF,INF,INF,INF,INF,INF},其中INF表示无限。现在选择最小距离值的顶点。我们选了节点0,将它加入到sptSet。所以sptSet变为{0}。加入0至sptSet后,更新其相邻顶点的距离值。0相邻的节点为1和6,他们的距离值便被更新成3和4。图中标示出在SPT的顶点显示为绿色。



gaitubao_2.jpg


        然后我们选择一个不包含在SPT里一个路径值为最小的一个节点,节点1被选了而且被加入到了sptSET,所以sptSET现在变为了{0,1}更新1临近节点的距离值,临近节点为2跟8,节点2跟8的距离值便变成了3+6=9、3+16=19。

gaitubao_3.jpg

        像上面一样选一个,我们选了节点6,加入到sptSet,所以sptSet变成了{0,1,6},更新节点6的临近节点的距离值,临近节点是5和7,更新后5:4+20=24,7:4+10=14.

gaitubao_3.jpg

            然后我们再选一个2加入,sptSet又新来了一个数字2,2的临近节点3和8便更新为11和26.

gaitubao_4.jpg

一直重复这些事儿直到sptset包含所有的节点:


gaitubao_5.jpg


gaitubao_6.jpg

最后,我们终于得到了一棵完整的最短路径树

 

gaitubao_8.jpg


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;

}

gaitubao_9.png

三、      Dijkstra最短路径算法的计算复杂度分析(最好、最差、平均情况复杂度):

(1) 最好的情况:每个顶点第一次检测到就是路径值就是最短路径。复杂度最低。

复杂度为:2n²+6n

(2) 最坏情况:顶点被检测了1次以上,并且每次检测都更新路径值为最小,即每次找的都不是最短路径,直到最后一次检测。复杂度最高

复杂度为:3n²+6n

(3) 平均情况复杂度:时间复杂度为O(n²)

四、      总结综合实验心得体会:

本次的Dijkstra最短路径算法在数据结构的课程上也接触过,所以感觉这个不成问题,选用的例子是自己随手画出来的,然后按照Dijkstra最短路径算法把流程步骤分别画了出来。然后其他部分参考了一下wiki以及geek论坛等国外大神的论文。还有很多东西老师在课堂上也给我们又讲了一遍,所以从算法思想上就不成多大问题了,主要是代码,而且必须得了解了算法才能mark得出代码来,否则根本无从下手。

版权声明:若无特殊注明,本文为《Chin》原创,转载请保留文章出处。
本文链接:https://www.qinor.cn/post-60.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框
可使用QQ号实时获取昵称+头像

私密评论

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!