大型网络单源的最短路的线性计算方法

1.一种大型网络单源的最短路的线性计算方法，其特征以标明相邻两地之间距离的图为基础，并采用下述步骤进行计算：第一步：令d(x)=-1，设N(x)={v1，v2，…，vk}为x的邻接点集，令：d(vi)=d(x，vi) i=1，2，…，k。再令X=N(X)，ω=ω’，min=min{d(v)｜v∈X}。如果min＞ω，则ω=min。进入第二步。第二步：对X中的每一个满足(按下标顺序进行)：d(vi)≤ω，i∈{1，2，…，k}。的点包括后来并入的点的邻接点集N(vi)={u1，u2，…，uk}的每一点处理如下：如果d(uj)≠0，且d(uj)＞d(vi)+d(vi，uj)则d(uj)=d(vi)+d(vi，uj)如果d(uj)=0则d(uj)=d(vi)+d(vi，uj)，k=k+1，vk=uj，X=X∪{vk}。当X中的点全部处理完，包括后来并入的点，然后进入第三步。第三步：划分X为Y和Z，其中Y={d(v)｜d(v)≤ω，v∈X}，Z={d(v)｜d(v)＞ω，v∈X}。如果止点y∈Y，则算法终止。否则令：X=Z，min=min{d(v)｜v∈X}，ω=ω+ω’。如果min＞ω则ω=min。设Z={v1，v2，…，vk}，转入第二步。

暂无