数据结构（单源最短路径）

朱雀 2022-06-05 04:35 224阅读 0赞

单源最短路径指的是找到A,B两点之间路径中权值之和最小的路径。  
**狄克斯特拉算法（Dikastra）**  
对于求单源点的最短路径问题，狄克斯特拉（Dikastra）提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法。狄克斯特拉的算法思想是：设置两个顶点的集合S和T，集 合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的最短路径长度值为原来的当前最短路径长度值与  
从源点过顶点u到达该顶点的新的最短路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加到集合S中为止。  
算法实现：

public void Dijkstra(ref bool[,] pathMatricArr, 
    ref int[] shortPathArr, Node<T> n) 
    { 
    int k = 0; 
    bool[] final = new bool[nodes.Length]; 
    //初始化 
    for (int i = 0; i < nodes.Length; ++i) 
    { 
    final[i] = false; 
    shortPathArr[i] = matrix[GetIndex(n),i]; 
    for (int j = 0; j < nodes.Length; ++j) 
    { 
    pathMatricArr[i,j] = false; 
    } 
    if (shortPathArr[i] != 0 && shortPathArr[i] < int.MaxValue) 
    { 
    pathMatricArr[i,GetIndex(n)] = true; 
    pathMatricArr[i,i] = true; 
    } 
    } 
    // n为源点 
    shortPathArr[GetIndex(n)] = 0; 
    final[GetIndex(n)] = true; 
    //处理从源点到其余顶点的最短路径 
    for (int i = 0; i < nodes.Length; ++i) 
    { 
    int min = int.MaxValue; 
    //比较从源点到其余顶点的路径长度 
    for (int j = 0; j < nodes.Length; ++j) 
    { 
    //从源点到j顶点的最短路径还没有找到 
    if (!final[j]) 
    { 
    /从源点到j顶点的路径长度最小 
    if (shortPathArr[j] < min) 
    { 
    k = j; 
    min = shortPathArr[j]; 
    } 
    } 
    } 
    //源点到顶点k的路径长度最小 
    final[k] = true; 
    //更新当前最短路径及距离 
    for (int j = 0; j < nodes.Length; ++j) 
    { 
    if (!final[j] && (min + matrix[k,j] < shortPathArr[j])) 
    { 
    shortPathArr[j] = min + matrix[k,j]; 
    for (int w = 0; w < nodes.Length; ++w) 
    { 
    pathMatricArr[j,w] = pathMatricArr[k,w]; 
    } 
    pathMatricArr[j,j] = true; 
    } 
    } 
    } 
    }