最短路径——迪杰拉斯算法

迪杰拉斯算法是求图的最短路径的一个常用算法。

  如图所示为一个 有权有向图                                                                                                 

假设起始点为V0，从起始点开始先去找与起始点距离最近的一个点—V2。再去找寻距离V2最近的点V3，若此时到达V3还有其他路径，需比较两种路径距离长短。值得注意的是，在构成最短路径时，不能形成闭合回路。

代码实现:

/**最短路径**/
void DIJ(Mraph *G,int v0)
{
    int i,j;
    int MinG;
    int dis[MAXN];///从起始点到某点的距离
    int vis[MAXN];///标记访问点
    for(i=0;i<MAXN;i++)
    {
        dis[i]=INF;///初始化
        vis[i]=0;///将VIS数组初始化为0，表示所有点未被访问
    }
    dis[v0]=0;///假设初始点为v0，v0到自身的距离为0
    int v;
    for(i=0;i<MAXN;i++)///找到离v0最近的点
    {
        MinG=INF;///当前已知离初始点最短的距离
        for(j=0;j<MAXN;j++)
        {
            if(!vis[j]&&dis[j]<MinG)///当这个顶点没有被访问，且起始点到顶点j的距离小于已知最短距离
            {
                MinG=dis[j];///更新MinG
                v=j;///将j的数值赋给v
            }
        }
        vis[v]=1;///标记顶点已经被访问
        for(j=0;j<MAXN;j++)
        {
            if(!vis[j]&&dis[v]+G->arcs[v][j]<dis[j])///如果j顶点未被访问，且从起始点到j的距离大于起始点到v的距离加上v到j的距离
            {
                dis[j]=dis[v]+G->arcs[v][j];///对dis进行更新
            }
        }
    }
}

运行结果：

（由于初始点为V0，所以无法访问V1）

时间复杂度：O（n²）

第一个for循环的时间复杂度为O（n），第二个for循环总共进行n-1次，时间复杂度为O（n）。所以总的时间复杂度为O（n²）。