数据结构——带权有向图（最短路径算法Dijkstra算法）

zieckey

1.Dijkstra
1)      适用条件&范围：
a)       单源最短路径(从源点s到其它所有顶点v);
b)       有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c)       所有边权非负(任取(i,j)∈E都有Wij≥0);
2)      算法描述：
a)       初始化：dis[v]=maxint(v∈V,v≠s); dis=0; pre=s; S={s};
b)       For i:=1 to n
1.取V-S中的一顶点u使得dis=min{dis[v]|v∈V-S}
2.S=S+{u}
3.For V-S中每个顶点v do Relax(u,v,Wu,v)
c)       算法结束：dis为s到i的最短距离；pre为i的前驱节点
3)      算法优化：
    使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。
    使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。
下面给出Java实现的源码：
               
               
                package zieckey.datastructure.study.graph;
/**
*
* 带权重有方向图
* 介绍了Dijkstra算法：最短路径算法
*
* Dijkstra算法原理：
*     1)      适用条件&范围：
        a)       单源最短路径(从源点s到其它所有顶点v);
        b)       有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
        c)       所有边权非负(任取(i,j)∈E都有Wij≥0);
    2)      算法描述：
        a)       初始化：dis[v]=maxint(v∈V,v≠s); dis=0; pre=s; S={s};
        b)       For i:=1 to n
                1.取V-S中的一顶点u使得dis=min{dis[v]|v∈V-S}
                2.S=S+{u}
                3.For V-S中每个顶点v do Relax(u,v,Wu,v)
        c)       算法结束：dis为s到i的最短距离；pre为i的前驱节点
    3)      算法优化：
        a)    使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。
        b)    使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。
*
*
* @author zieckey
*
*/
public class WeightedDirectedGraph
{
    private final int            MAX_VERTS    = 20;
    private final int            INFINITY    = 1000000;
    private Vertex[]            vertexList;            // list of vertices
    private int[][]                adjMat;                // adjacency matrix
    private int                    nVerts;                // current number of vertices
    private int                    nTree;                    // number of verts in tree
    private DistanceParent[]    shortestPath;                    // array for shortest-path data
    private int                    currentVertex;            // current vertex
    private int                    startToCurrentDistance;        // distance to currentVert
   
    public WeightedDirectedGraph()
    {
        vertexList = new Vertex[MAX_VERTS];
        // adjacency matrix
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        nTree = 0;
        for ( int j = 0; j  MAX_VERTS; j++ )
        {
            // set adjacency
            for ( int k = 0; k  MAX_VERTS; k++ )
            {
                adjMat[j][k] = INFINITY;
            }
        }
        
        shortestPath = new DistanceParent[MAX_VERTS]; // shortest paths
        
    }
    /**
     * 求最短路径算法：Dijkstra算法。
     */
    public void findShortestPath()
    {
        int startTree = 0;//从0节点开始
        vertexList[startTree].isInTree = true;//将该节点放入树中
        nTree = 1;
        
        //初始化最短路径表，以邻接矩阵中的 startTree 行数据初始化
        for ( int i = 0; i  nVerts; i++ )
        {
            shortestPath = new DistanceParent( startTree, adjMat[startTree] );
        }
        
        while( nTree  nVerts )
        {
            int indexMin = getMinFromShortestPath();// 从最短路径表中得到目前的最小值
            int minDist = shortestPath[indexMin].distance;
            
            if ( minDist == INFINITY ) // 如果为 INFINITY ，表明不可达，或者都在树中了。
            {
                System.out.println( "There are unreachable vertices" );
                break; // sPath is complete
            } else
            {
                currentVertex = indexMin; // 将最小的赋值给currentVert，为即将进入树中作准备
                startToCurrentDistance = shortestPath[indexMin].distance;//路径权重最小
            }
            // 将当前节点放入树中
            vertexList[currentVertex].isInTree = true;
            nTree++;
            adjust_sPath(); // 更新最短路径表
        }//end while
        
        displayPaths(); // display sPath[] contents
        
        nTree = 0; // clear tree
        for(int j=0; jnVerts; j++)
        {
            vertexList[j].isInTree = false;
        }
    }
   
    /**
     * 显示最短路径
     */
    public void displayPaths()
    {
        for ( int j = 0; j  nVerts; j++ ) // display contents of sPath[]
        {
            System.out.print( vertexList[j].label + "=" ); // B=
            if ( shortestPath[j].distance == INFINITY )
            {
                System.out.print( "inf" ); // inf
            }
            else
            {
                System.out.print( shortestPath[j].distance ); // 50
            }
            char parent = vertexList[shortestPath[j].parentVert].label;
            System.out.print( "(" + parent + ") " ); // (A)
        }
        System.out.println( "" );
    }
    /**
     * 更新最短路径表
     */
    public void adjust_sPath()
    {
        for ( int column=1; column  nVerts;column++ )//跳过自身，从1开始
        {
            if ( false == vertexList[column].isInTree )//如果不在树中
            {
                // calculate distance for one sPath entry
               
               
                int currentToFringe = adjMat[currentVertex][column];// 当前点到column的距离
                int startToFringe = startToCurrentDistance + currentToFringe;//计算起始点到column的距离
               
                // 与原来最短路径表中的权重值进行比较
                if ( startToFringe  shortestPath[column].distance ) // 如果新值更小，就更新最短路径表
                {
                    shortestPath[column].parentVert = currentVertex;
                    shortestPath[column].distance = startToFringe;
                }//end if
            }//end if
        }//end for
    }
    /**
     * 从最短路径表中得到目前的最小值
     * @return 返回最小值的index
     */
    public int getMinFromShortestPath()
    {
        
        int minDist = INFINITY; // assume minimum
        int indexMin = 0;
        for ( int j = 1; j  nVerts; j++ ) // for each vertex,
        { // if it's in tree and
            if ( !vertexList[j].isInTree && // smaller than old one
                    shortestPath[j].distance  minDist )
            {
                minDist = shortestPath[j].distance;
                indexMin = j; // update minimum
            }
        } // end for
        return indexMin;
    }
   
    /**
     * 添加一条边
     * @param start 边的起点
     * @param end   边的终点
     * @param weight 边的权重
     */
    public void addEdge( int start, int end, int weight )
    {
        adjMat[start][end] = weight;    //有方向
    }
   
    /**
     * 添加一个节点
     *
     * @param lab
     */
    public void addVertex( char lab ) // argument is label
    {
        vertexList[nVerts++ ] = new Vertex( lab );
    }
}
其他类：
package zieckey.datastructure.study.graph;
/**
* 在最短路径问题中，保存距离和到达该节点前最后一个必经节点
*
* @author zieckey
*/
public class DistanceParent
{
    public int    distance;    // distance from start to this vertex
    public int    parentVert; // current parent of this vertex
    public DistanceParent( int pv, int d ) // constructor
    {
        distance = d;
        parentVert = pv;
    }
}
===
package zieckey.datastructure.study.graph;
/**
*
* 图中的(节)点。
*
* @author zieckey
*
*/
class Vertex
{
    public char        label;        // label (e.g. 'A')
    public boolean    wasVisited;
    public boolean    isInTree;
    public Vertex( char lab ) // constructor
    {
        label = lab;
        wasVisited = false;
        isInTree = false;
    }
} // end class Vertex


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16292/showart_529517.html