张淑敏　王元芬

(1.青海师范大学数学系　西宁　810008)(2.虎台中学　西宁　810008)



基于Dijkstra算法最短路问题C语言实现

张淑敏1王元芬2

(1.青海师范大学数学系西宁810008)(2.虎台中学西宁810008)

在日常生活和生产中最短路问题是重要的优化问题之一,而Dijkstra算法是目前公认的解决最短路径问题较好的算法。论文采用C语言编程来实现使用Dijkstra算法求解最短路问题。

最短路问题; Dijkstra算法; C语言

Class NumberTP301.6

1　引言

在日常生活和工作中,为了取得最大的利益或者节约更多的成本,人们都在试图用最简单的方法找出尽可能短的路程到目的地,例如铺设管道中为了节约成本而规划最合理的铺设方法,出门旅游选择合适的出游路线和出游方式等。这些问题都可以划归为最短路径问题,尽可能快地计算最短路径是我们生活的迫切需求。求最短路有两种算法,一是求从某一点到其他各点之间最短距离的Dijkstra算法,二是求网络图上任意两点之间最短距离的矩阵算法[2]。本文主要解决最短路径的Dijkstra算法的计算,利用其思想编写计算机程序,辅助完成最短路径问题的求解[4]。并且进一步熟悉最短路径问题的Dijkstra算法,掌握其思想,并会利用其算法解决一些优化问题。在用C语言编程中,体会利用简单语句就可以解决复杂问题的好处。

2　基本知识

2.1Dijkstra算法

Dijkstra算法是由E.W.Dijkstra于1959年提出,又叫迪杰斯特拉算法,它应用了贪心算法模式,是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题,其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。……