Dijkstra最短路算法

http://blog.51cto.com/ahalei/1387799

/// <summary>
    /// Gets the shortest path from the starting Node to the ending Node.
    /// </summary>
    /// <returns>The shortest path.</returns>
    /// <param name="start">Start Node.</param>
    /// <param name="end">End Node.</param>
    public virtual Path GetShortestPath ( Node start, Node end )
    {
        
        // We don't accept null arguments
        if ( start == null || end == null )
        {
            throw new ArgumentNullException ();
        }
        
        // The final path
        Path path = new Path ();

        // If the start and end are same node, we can return the start node
        if ( start == end )
        {
            path.nodes.Add ( start );
            return path;
        }
        
        // The list of unvisited nodes
        List<Node> listUnVisited = new List<Node> ();
        
        // Previous nodes in optimal path from source
        Dictionary<Node, Node> dictPrevious = new Dictionary<Node, Node> ();
        
        // The calculated distances, set all to Infinity at start, except the start Node
        Dictionary<Node, float> dictDistances = new Dictionary<Node, float> ();
        //我们将此时dictDistances数组中的值称为最短路的“估计值”。
        for ( int i = 0; i < m_Nodes.Count; i++ )
        {
            Node node = m_Nodes [ i ];
            listUnVisited.Add ( node );
            
            // Setting the node distance to Infinity
            dictDistances.Add ( node, float.MaxValue );
        }
        
        // Set the starting Node distance to zero
        dictDistances [ start ] = 0f;
        while ( listUnVisited.Count != 0 )
        {
            
            // Ordering the unvisited list by distance, smallest distance at start and largest at end
            listUnVisited = listUnVisited.OrderBy ( node => dictDistances [ node ] ).ToList ();
            
            // Getting the Node with smallest distance
            Node current = listUnVisited [ 0 ];
            
            // Remove the current node from unvisisted list
            listUnVisited.Remove ( current );
            //通过一轮更新过dictDistances数组，当前离start 最近是current。此时，current的值已经从“估计值”变为了“确定值”。
            // When the current node is equal to the end node, then we can break and return the path
            if ( current == end )
            {
                
                // Construct the shortest path
                while ( dictPrevious.ContainsKey ( current ) )
                {
                    
                    // Insert the node onto the final result
                    path.nodes.Insert ( 0, current );
                    
                    // Traverse from start to end
                    current = dictPrevious [ current ];
                }
                
                // Insert the source onto the final result
                path.nodes.Insert ( 0, current );
                break;
            }
            
            // Looping through the Node connections (neighbors) and where the connection (neighbor) is available at unvisited list
            for ( int i = 0; i < current.connections.Count; i++ )
            {
                Node neighbor = current.connections [ i ];
                
                // Getting the distance between the current node and the connection (neighbor)
                float length = Vector3.Distance ( current.transform.position, neighbor.transform.position );
                
                // The distance from start node to this connection (neighbor) of current node
                float alt = dictDistances [ current ] + length;
                
                // A shorter path to the connection (neighbor) has been found
                if ( alt < dictDistances [ neighbor ] )
                {
                    dictDistances [ neighbor ] = alt;
                    dictPrevious [ neighbor ] = current;
                }
            }
        }
        path.Bake ();
        return path;
    }