dijkstra，dijkstra算法的作用

一、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算法只能用于无向图吗

也可以用于无向图,在无向图G=(V,E)中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短路径。

三、dijkstra算法的优缺点

Dijkstra算法算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。

Dijkstra算法运行时的优点主要是：算法简明、能得到最优解。

算法的主要缺点是：算法运算效率低（特别是有时候不需要最优解）、运算中占用空间大