摘要长时间以来，最短路算法一直是科学研究的焦点，最短路问题在众多领域都有应用，比如交通运输网路等。随着交通运输网路的不断发展扩张，网路中的最短路问题也具有重大理论意义和应用价值。87194

    关于最短路算法的问题有很多种类，目前国内外公认的经典的算法有Dijkstra及Floyd算法。在这两种算法中，它们的网路被抽象成图论中定义的有向图和无向图，可以用图的点的邻接矩阵来记录点间的相关信息。当进行图的遍历来搜索最短路径的时候，应该以该矩阵为基础来不断进行目标值最小性判别，从而获得最后的最优路径。本文先介绍了几种研究中常见最短路算法，然后再着重介绍了Dijkstra，Floyd两种算法，并通过实例对两种算法进行研究。然后对两种算法进行比较，分析每种算法的各自的优势及劣势。

毕业论文关键词：最短路算法；Dijkstra算法；Floyd算法

Abstract All along, the shortest path algorithm is the focus of science research, the shortest path problem has been applied in many fields, such as transportation network, etc。。 With the continuous development and expansion of the transportation network, the shortest path problem in the network also has great theoretical significance and application value。

There are many kinds of problems about the shortest path algorithm , and Dijkstra and Floyd algorithms are the most classic and wildly accepted all aroud the world。 In these two algorithms, the network is abstracted as a directed or undirected graph defined in graph theory, which uses the adjacent matrix of nodes to record the correlation information 。 In order to search the shortest path, the matrix is the basis for the continuous optimization of the target value, until the final optimization path is obtained。 This paper first introduces the common shortest path algorithm, focuses on the two algorithms:Dijkstra and Floyd and then by comparing the two results of two examples, we can deduce that each algorithm has its own advantages and disadvantages。

Keywords: the shortest path algorithm; Dijkstra algorithm;Floyd algorithm

目  录

第一章 绪论 -1

  1。1 研究背景1

  1。2 交通运输网路的最短算短算法的优劣讨论的研究意义1

  1。3 交通运输网路的最短算短算法的优劣讨论的国内外研究现状与发展1第二章 最短路算法知识-3               

  2。1 最短路3

  2。2 最短路算法3

  2。3 两种经典算法6

第三章最短路问题的不同算法及讨论-10

  3。1 Floyd算法最短路问题-10     

  3。2 Dijkstra算法最短路问题-15 

  3。3 两种算法的优劣比较-19结论20致谢21参考文献-22

第一章 绪论

1。1 研究背景

  在二十世纪中的后期，计算机的出现和发展，使得对图论的研究越来越热烈，其中的一个经典问题便是最短路问题。最早给出最短路算法的是荷兰数学家Dijkstra，该算法就叫做Dijkstra算法。随着交通运输网路的不断发展发展，Dijkstra算法不能满足于所有的情况，因此学者们又研究探索出了许多新的算法。这些算法中经典的有Floyd算法，A*算法，遗传算法等。虽然算法的种类很多，但它们的目的都是在于寻找图中两点间的最短路径。最短路问题常应用于众多领域，例如交通运输网路之类。网路中的最短路问题也具有重大理论意义和应用价值。也因为所涉及的领域众多，所以每种算法都有其适用的情况，选择正确的算法事半功倍，选择不适合的就事倍功半。所以对算法的优势和劣势进行讨论很有必要。