Dijksra 单源最短路

原理不再赘述，请参阅Dijkstra算法

本文对该算法进行伪码实现。

一、算法之前的准备：

1、选择图的存储方式：邻接表。

对于稠密图，也可考虑邻接矩阵。
邻接表相对邻接矩阵的优点：

  • 1）节约存储空间。
  • 2）可以自由的将每个邻接链排序处理（比如可以按权值、按结点序号排序），可以进一步优化，降低复杂度。

缺点很显然，邻接表写起来麻烦。（伪码倒是不麻烦）

邻接表的设定：
Head:主表
Head[v]: 编号为v的点
adjacent(Head[v]): 编号为v的点的第一个邻接点指针。

设p = adjacent(Head[v]),则：
VerAdj(p): p的结点编号
cost(p):<v，VerAdj(p)>p的权重
link(p): v的下一个邻接点地址。

2、其他需要存储的内容：

1）如何将结点收录到S集合中？
设定数组s。s[i] = 1表示i号点已被收录
2）如何记录距离？
设定数组dist。dist[i] = m 表示i号点与起点距离为m
3）如何记录路径？
设定数组path。path[i]= j表示路径中i的前一个结点是j。

二、伪码：

算法 DSPath(Head,n,v.dist,path)
/*计算v到其他顶点的最短路径，n表示顶点个数*/
DSPath1.[初始化]
    FOR i = 1 TO n DO {
    path[i] = -1.
    dist[i] = max.
    s[i] = 0.
    }
    dist[v] = 0.
    s[v] = 1.
    p = adjacent(Head[v]).
    u = v.
DSPath2.[算！]
    FOR j = 1 TO n DO{  //循环n次。能保证把所有可收录结点均收录
        WHILE p ≠ NULL DO{//遍历u结点所有邻接的结点，并更新dist/path值
        k = VerAdj(p).   
        IF(s[k] ≠ 1 AND dist[u] +cost(p) ＜ dist[k]) THEN{
            dist[k] = dist[u] + cost(v).
            path[k] = u.
            }
        p = link(p).
        }//u是上一次循环新收录的结点。注意：收录u之后，仅有与u相邻的结点的dist、path值才可能改变。其他点的数据不会改变！
        ldist = max.
        FOR i = 1 TO n DO{
            IF (dist[i]<ldist AND s[i]=0) THEN{
            ldist = dist[i].
            u = i.
            }//找到dist最小的点并收录。更新u

        }
        s[u] = 1.
        p = adjaecnt(Head[u]).
    }

Floyd 多源最短路

定义矩阵A[n][n],A[i][j]为i点到j点的最短距离