• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

最短路径dijkstra,floyd

算法笔记 站点默认 2周前 (11-28) 13次浏览 已收录 1个评论
文章目录[隐藏]

最短路径分为两类,单元最短路径和多源最短路径。

单源最短路径

无权图的单源最短路径

这里我先说一下我的理解,我们求一个顶点到其它各顶点的最短路径,那么肯定得用bfs算法来遍历。之前的图的遍历和应用中,dfs用了很多,那么现在完全就是类比的概念了,在求两个顶点u,v的路径长度的时候,我们给dfs加了两个形参终点v和长度的d,那么这个bfs的算法也是类是的,不过我们得需要一个数组存储每个顶点到原点的距离,因为是遍历所有的顶点,那么形参v就可以省去了,此时我们需要带一个形参数组进去吗??其实大可不必,别忘了我们还有visited(标记数组),我们完全可以用它来存储数据,(那么标记的作用岂不是消失了?)并没有,我们初始值,设为一个一看就不是该顶点到初始顶点的距离的数,比如-1,这样当我们存储改顶点到初始顶点的值进去了,直接判断大于0即可,别忘了,我们还需要一个数组来存储路径,(岂不是需要n个数组来记录n个顶点到源点的路径)根本不用,我们只需要一个数组,数组下标对应的每个顶点中存储它上一步的顶点,即是从哪个顶点过来的,这样当我们需要输出从源点到x点的路径的时候,我们只需要输出数组下标x,对应的值就是从某个顶点过来的,如此追踪即可,这是反的路径,我们可以压入栈中,在将其输出。
/* 邻接表存储 - 无权图的单源最短路算法 */
 
/* dist[]和path[]全部初始化为-1 */
void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
{
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
     
    Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
    dist[S] = 0; /* 初始化源点 */
    AddQ (Q, S);
 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q);
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
                dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                AddQ(Q, W->AdjV);
            }
    } /* while结束*/
}

有权图的单源最短路径

这个时候就有一个金光闪闪的算法了dijkstra算法
问题描述
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
Dijkstra算法的解决方案
Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
Dijkstra算法的解题思想
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中,S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点,并加入到集合S中,并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点,并视从源点v出发的所有边为到各顶点的最短路径(确定数据结构:因为求的是最短路径,所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时,dist是源点v到顶点i的直接边长度,即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点)。
2、在上述的最短路径dist[]中选一条最短的,并将其终点(即)k加入到集合s中。
3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后,源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j],取其中的较小者。
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中,再回去到第三步,如此重复,直到集合S中的包含图G的所有顶点。
/* 邻接矩阵存储 - 有权图的单源最短路算法 */
 
Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    int MinDist = INFINITY;
 
    for (V=0; V<Graph->Nv; V++) {
        if ( collected[V]==false && dist[V]<MinDist) {
            /* 若V未被收录,且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在,返回错误标记 */
}
 
bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;
 
    /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* 先将起点收入集合 */
    dist[S] = 0;
    collected[S] = true;
 
    while (1) {
        /* V = 未被收录顶点中dist最小者 */
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;      /* 算法结束 */
        collected[V] = true;  /* 收录V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( Graph->G[V][W]<0 ) /* 若有负边 */
                    return false; /* 不能正确解决,返回错误标记 */
                /* 若收录V使得dist[W]变小 */
                if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                    dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                    path[W] = V; /* 更新S到W的路径 */
                }
            }
    } /* while结束*/
    return true; /* 算法执行完毕,返回正确标记 */
}

多元最短路径

floyd算法

太难了,学了好半天,这个算法实在是不想看了,,

核心思路编辑
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 [3]
从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术(松弛操作),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
状态转移方程
其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};
map[i,j]表示i到j的最短距离,K是穷举i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。
当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路。
算法过程编辑
1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。 [4]
时间复杂度与空间复杂度编辑
时间复杂度:O(n^3);
空间复杂度:O(n^2)

* 邻接矩阵存储 - 多源最短路算法 */
 
bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;
 
    /* 初始化 */
    for ( i=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }
 
    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                        return false; /* 不能正确解决,返回错误标记 */
                    path[i][j] = k;
                }
    return true; /* 算法执行完毕,返回正确标记 */
}

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:最短路径dijkstra,floyd
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽