?引子：
谈到到算法，我们第一个需要知道的概念就是，究竟什么是算法。所谓算法，从字面意思上来讲就是进行“算”的方法，通俗点讲就是一套解决某种特定系列问题的模版，就好比鸡兔同笼问题总是有一种固定的解题步骤一样，算法也是系统的解决问题的手段，是一种策略。
?了解一个算法，我们需要从以下几个方面来切入：
（1）算法的起源
（2）算法描述[文字描述、代码描述]
（3）算法原理
（4）算法应用[底层应用和顶层应用]
?算法的起源：从算法的名称不难看出算法与一个叫做迪杰斯特拉的人关系非同寻常，Dijkstra算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的，为了纪念他，将该算法命名为迪杰斯特拉算法。
?算法描述：
- 文字描述：初始化选择一个起始点，从起始点开始采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展结束。
?算法原理：
我们需要先假设一个背景：假设现在有U、V、W、X、Y、Z五个点，我们想要知道任意一个点到其他所有点的最短距离。我们假设以U作为起始点，想要知道U到其他剩余的四个点的最短距离。Step1首先需要确定U与剩下的四个点有没有直接联系，也就是剩余的几个点中有哪些点是U的下一个节点或者说邻接点。假设V、W、X与U有着直接联系，那么我们可以直接看出来U与V、W、X的路径关系。假设Y、Z我们认为跟U没有直接相连，而是经过了其他的点的中转，那么它与U的初始路径我们认为是∞。Step2选择有路径当中的最短的一项，确定其是哪个节点，然后以该节点为新的起始节点，更新当前状态，那么我们首先需要保留该节点的上一节点到该节点的距离，作为初始权值，从当前节点开始无论是指向任意节点都需要加上权值。每次都会产生新的路径大小的值，我们需要和之前的进行比较，如果比之前的大，那么我们就保留之前的，若比之前的小则更新为当前路径大小值，在更新路径大小值的同时我们需要更新节点，就是经过了哪个节点。来回往复，直至找完最后一条最短路径，结束。我们通过一个具体的图来理解：
问题1：以U作为起点，求出U到其他点的最短路径。
分析1：与U直接相连的有V和X两个节点，那么我们可以知道U->V的dist为2，U->X的dist为1，U->W的dist为5先不考虑其他节点之间的关系，U到其他节点的dist为∞。因为dist（x）小于dist（v）且dist（v）小于dist（w）那么我们将X作为当前的起始节点，另外需要附上X的权值为1。接下来同样的方法找出X与其他剩余节点之间的dist，然后经过判定，最终得到最短路径。
解答1:
?算法应用：（最短路径问题）
在此我将给出一个解决实际问题的案例——重庆轻轨出行路径规划系统
在计算机 络中的应用则更加实体化：
为了得到从任意一个路由器出发，到其他路由器的最短路径。 就需要构造一个无向带权图，来应用Dijkstra算法，首先我们确定顶点、边和边的权重这三个元素。在计算机 络中，我们将路由器作为顶点，两个路由器之间的线路作为边，传输延迟、路由器跳数、物理距离等作为边的权重。然后可以将计算机 络中的问题抽象为图论，根据上述方法来得出最短路径问题。
?写在最后：迪杰斯特拉算法是非常重要且经典的算法，在数据结构和计算机 络课程中均有学习，理解迪杰斯特拉算法的核心思想有助于我们更深入的认识计算机，同时也帮助我们丰富武装了算法意识，作为计算机发展史上占据重要地位的算法，我们很有必要系统的认识。
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34686 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！