鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 操作系统维护 > 其它 > >

单源最短路径问题-Dijkstra算法

来源:互联网 作者:佚名 时间:2017-09-06 09:22
同样是层序遍历,在每次迭代中挑出最小的设置为已知 dijkstra算法是求带权单顶点到其他顶点的最短路径问题 表初始化 void InitTable(Vertex Start, Graph G, Table T) { int i; ReadGraph(G, T); for (i= 0 ; iNumVertex; i++ ) { T[i].Known = False; T[i].

同样是层序遍历,在每次迭代中挑出最小的设置为已知

dijkstra算法是求带权单顶点到其他顶点的最短路径问题

表初始化

void InitTable(Vertex Start, Graph G, Table T) {
    int i;
    ReadGraph(G, T);
    for (i=0; i<NumVertex; i++) {
        T[i].Known = False;
        T[i].Dist = Infinity;
        T[i].Path = NotAVertex;
    }
    T[Start].dist = 0;
}

 

显示实际路径

void PrintPath(Vertex V, Table T) {
    if (T[V].Path != NotAVertex) {
        PrintPath(T[V].Path, T);
        printf(" to");
    }
    printf("%v", V);
}

 

算法伪代码

void Dijkstar(Table) {
    Vertex V, W;
    for (;;) {
        V = smallest unknown distance vertex;
        if (V == NotAvertex) 
            break;
        T[V].Known = True;
        for each W adjacent to V
            if (!T[W].Known)
                if (T[V].Dist + Cvw < T[W].Dist) {
                    Decrease(T[W].Dist);
                    T[W].Path = V;
                }
    }
}

 

网友评论
<