当前位置：首页 > article >正文

迪杰斯特拉（Dijkstra）算法

article 2025/2/3 5:03:59

一、迪杰斯特拉--算法思想

按从某顶点到其它顶点的路径长度递增的方式,逐渐求到各顶点的最短路径。

设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。

设下一条最短路径终点为Vj ，则Vj只有：

◆ 源点到终点有直接的弧<Vs，Vj>；

◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。

若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：

dist[i]=Min{ dist[k]| Vk∈V-S }

利用上述公式就可以依次找出下一条最短路径。

二、迪杰斯特拉算法--数据组织

• 数据源

• 已确定结点集 S

• 待选结点集 V-S

• 结点临时最短路径长度

• 结点临时最短路径

三、迪杰斯特拉算法—步骤

① 令S={Vs} ，用带权的邻接矩阵表示有向图，对图中每个顶点Vi按以下原则置初值：

② 选择一个顶点Vj ，使得：

Distance[j]=Min{ Distance[k]| Vk∈V-S }

Vj就是求得的下一条最短路径终点，将Vj 并入到S中，即S=S∪{Vj} 。

③ 对V-S中的每个顶点Vk ，修改dist[k]，方法是：

若Distance[j]+Wjk<Distance[k]，则修改为：

Distance[k]=Distance[j]+Wjk ("Vk∈V-S )

④ 重复②，③，直到S=V为止。

四、迪杰斯特拉算法—实现

void Dijkstra(MGraph g,int start, int end)
{
    int dist[MAXV], path[MAXV];
    int s[MAXV];
    int mindis, i, j, u;
    for(i = 0; i < g.n; i ++)
    {
        dist[i] = g.edges[start][i];//dist数组初始化
        s[i] = 0;
        if(g.edges[start][i] < INF) 
			path[i] = start;
        else 
			path[i] = -1;        // path数组初始化
    } 
    s[start] = 1;                       //顶点start加入顶点集合s
	path[start] = 0;

    for(i = 0; i < g.n; i ++)//选择不在集合s中且具有最短路径的顶点
    {
        mindis = INF;
        for(j = 0; j < g.n; j ++)
        {
            if(s[j] == 0 && dist[j] < mindis)
            {
                u = j;
                mindis = dist[j];
            }    
        }    
s[u] = 1;//将顶点u加入集合
        for (j = 0; j < g.n; j ++)//修改dist和path
        {
            if (s[j] == 0)
            {
				if ((g.edges[u][j] < INF) && (dist[u] + g.edges[u][j] < dist[j]))
                {
                    dist[j] = dist[u] + g.edges[u][j];
                    path[j] = u;
                }    
            }    
        }    
    } 
    Dispath(g, dist, path, s, g.n, start, end);     
}