dijkstra算法过程表格(dijkstra算法步骤例题表格)

一、dijkstra算法是干什么的

SPF算法也被称为Dijkstra算法，这是因为最短路径优先算法SPF是由荷兰计算机科学家狄克斯特拉于1959年提出的。

SPF算法将每一个路由器作为根（ROOT）来计算其到每一个目的地路由器的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在SPF算法中，被称为最短路径树。

二、dijkstra算法计算过程

Dijkstra算法具体步骤如下。

1.

初始时，S只包含源点，即S＝{v}，v的距离dist[v]为0。U包含除v外的其他顶点，U中顶点u距离dist[u]为边上的权值（若v与u有边）或∞（若u不是v的出边邻接点即没有边<v，u>）。

2.

从U中选取一个距离v(dist[k])最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。

3.

以k为新选择的中间点，修改U中各顶点的距离；若从源点v到顶点u（u∈U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权值（即如果dist[k]+w[k，u]<dist[u]，那么把dist[u]更新成更短的距离dis

三、dijkstra最短路径算法步骤

1.Dijkstra最短路径算法步骤分为初始化、找到最短路径、更新节点的距离值三部分。

2.初始化包括将除起点外的所有路径设为无穷大，包括起点的距离为0。

找到最短路径需要选择当前未确定最短路径的节点中距离最小的节点进行松弛操作，即更新该节点可到达节点的距离值。

更新节点的距离值是在松弛操作中调整节点距离值，更新距离值后，以该节点为中心，重复找到最短路径。

3.Dijkstra算法属于贪心算法，计算结果不受负边权影响，但不能处理负权环。

该算法不适合于大规模的图，复杂度较高，但在小规模稠密图处理中性能较佳。