简单讲，Dijkstra算法是计算一个非负权图中，某个起始源点到其它所有节点的最短路径值，即求单源最短路径，经改进能够求出最短路径节点顺序。
首先，每个节点都存有一个值，这里简称节点值，表示当前节点到源点的最短距离，这个值是动态的，可以被更新，初始时，若节点与源点相连，则最短距离就是该路径距离，否则设为“无穷大”。 设整个图所有节点集合为E,已求得最短路径的节点集合为S,从源点开始，将源点加入集合S,在E-S(E中不含S中的节点的集合)中寻找最小节点值的节点，将该节点加入集合S中，然后进行松弛操作，即更新E-S中所有与新加入S节点相连的节点值，重复这个过程，即不断寻找E-S中最小的节点值，加入S，同时更新与这个节点相连的未加入S中的节点的节点值，对于n阶图，重复n-1此即可找出所有点到源点的最小距离，因为每一次操作都能找到一个节点到源点的最小距离。 这里有两个问题：如何更新节点值？为什么每次在E-S中的最小节点值就是该节点的最终最小值？
假设当前加入S的节点是 v 1 v_1 v1，与 v 1 v_1 v1相连的节点有 v 2 v_2 v2、 v 3 v_3 v3、 v 4 v_4 v4， v 2 v_2 v2在集合S中，则不考虑，因为v2肯定比v1先加入集合S，那么v2的节点值一定比v1小。如下如所示： 每个节点有节点名称和最短距离，节点与节点之间有距离，v1与v2已在S中，不考虑。用d[节点]表示该节点的节点值，w[a][b]表示节点a与节点b的距离。现在新加入的节点是v1,对于v3来说， d [ v 1 ] + w [ v 1 ] [ v 3 ] = 4 + 4 = 8 d[v1]+w[v1][v3]=4+4=8 d[v1]+w[v1][v3]=4+4=8 这个值比节点v3本身的值9要小，所以更新节点v3的值。 对于节点v4来说， d [ v 1 ] + w [ v 1 ] [ v 4 ] = 4 + 4 = 8 d[v1]+w[v1][v4]=4+4=8 d[v1]+w[v1][v4]=4+4=8 这个值比节点v4本身的值5要大，所以不更新节点v4的节点值。 更新完结果就是： 这样的更新也叫松弛操作，就是我发现通过另一个节点到达源点比我原来的路径到达源点更近，我就更新我的最短路径，否则就不更新，通用算法就是：
S = S ∪ v 0 / / 将 v 0 加 入 集 合 S S=S\cup v_0 //将v_0加入集合S S=S∪v0//将v0加入集合S f o r v i i n E − S for\quad v_i\quad in\quad E-S forviinE−S i f d [ v 0 ] + w [ v 0 ] [ v i ] < d [ v i ] \qquad if\quad d[v_0]+w[v_0][v_i]<d[v_i] ifd[v0]+w[v0][vi]<d[vi] d [ v i ] = d [ v 0 ] + w [ v 0 ] [ v i ] \qquad \qquad d[v_i]=d[v_0]+w[v_0][v_i] d[vi]=d[v0]+w[v0][vi]
算法中遍历的是所有E-S中的点，但可以对于那些不与新加入的点相连的点，其w[][]距离是无穷大，所以不影响结果。
这个问题与Dijkstra算法正确性挂钩，现在就来证明一下： （1）因为每次都是找的E-S中的最小节点值的点加入S，那么加入S的顺序一定是节点到源点最小距离的顺序。 （2）每次加入S的节点 v v v一定与S中的节点直接相连，若不然，则存在中间节点 v j v_j vj连接集合S和点 v v v，那么 v j v_j vj一定有比 v v v更小的节点值，与 d [ v ] d[v] d[v]最小矛盾。 （3）对于一个已求得部分节点最短距离的S集合，下一个加入集合S中的节点必然是S集合中节点的下一邻接点，而根据算法特性，S集合中节点的下一邻接点都被进行松弛更新过，所以E-S中的最小节点值一定是该节点的最短距离。（注意，这里找最小值是为了便于计算，有可能有多个节点的最短距离已经产生，今后也不会再更新，只是他们距离更大一些，所以暂时不被选择）。 简单地说，因为下一个最短距离的节点必然是S集合的下一邻接点，而选择E-S中最小节点值的节点恰能满足该节点是S的下一邻接点，所以该节点值一定是最短距离。
S = { s } / / 源 点 加 入 集 合 S S=\{s\}//源点加入集合S S={s}//源点加入集合S w h i l e n − 1 > 0 while\quad n-1>0 whilen−1>0 v t = f i n d M i n ( E − S ) / / 在 E − S 中 找 到 最 小 距 离 的 节 点 \qquad v_t=findMin(E-S) \qquad//在E-S中找到最小距离的节点 vt=findMin(E−S)//在E−S中找到最小距离的节点 S = S ∪ v t / / 将 v t 加 入 集 合 S \qquad S=S\cup v_t \quad \quad \quad \quad \qquad//将v_t加入集合S S=S∪vt//将vt加入集合S f o r v i i n E − S / / 在 更 新 节 点 值 \qquad for\quad v_i\quad in\quad E-S \qquad//在更新节点值 forviinE−S//在更新节点值 i f d [ v t ] + w [ v t ] [ v i ] < d [ v i ] \qquad \qquad if\quad d[v_t]+w[v_t][v_i]<d[v_i] ifd[vt]+w[vt][vi]<d[vi] d [ v i ] = d [ v t ] + w [ v t ] [ v i ] \qquad \qquad \qquad d[v_i]=d[v_t]+w[v_t][v_i] d[vi]=d[vt]+w[vt][vi] n = n − 1 \qquad n=n-1 n=n−1
以下图为例： 以v1为起始源点，求其余各点到v1的最短距离。后面演示中，用绿色标记加入集合S中的节点，用棕色标记松弛更新的节点。 第一步：选最小的d[v1]=0,源点v1加入S，同时更新d[v2]=2,d[v3]=3 第二步：选最小的d[v2]=2,v2入S，同时更新d[v4]=d[v2]+9=11,d[v3]=3(不变，因为d[v3]<d[v2]+5) 第三步：选最小的d[v3]=3,v3加入S，同时更新d[v4]=d[v3]+4=7,d[v5]=d[v3]+1=4. 第四步：选最小的d[v5]=4,v5加入S，同时更新d[v4]=d[v5]+2=6,d[v6]=d[v5]+4=8 第五步：选最小的d[v4]=6,v4加入S，同时更新d[v6]=8 第六步：只剩v6了，直接将其加入S
