Dijkstra：最短路径计算 - 面向对象

• 下载演示项目 - 11.23 KB
• 下载源代码 - 67.36 KB

引言

Dijkstra 是一位荷兰计算机科学家，他发明了一种快速简便的方法来计算两点之间的最短路径。我在互联网上找到的许多例子都实现了该算法，但没有一个是以面向对象的方式完成的。所以我想自己做一个。

背景

关于 Dijkstra 的信息可以在 这里 找到。

Using the Code

代码包含两个 Project 类

1. GUI：直观地显示信息
   • 要添加位置，请单击“添加位置”按钮，然后单击要在地图上添加位置的位置。
   • 要添加路径，请单击“添加位置”按钮以停用添加位置，然后单击起始位置，然后单击结束位置。路径的权重可以在顶部配置。
2. RouteEngine：计算路径

我将只详细介绍 RouteEngine。对于这篇文章来说，UI 的处理方式并不重要，但如果您需要关于它的信息，您可以随时提问。

项目 RouteEngine

1. Connection：此类保存有关两点之间连接的信息。这是一个从 A（起始点用点直观显示）到 B 的单向连接，并附带一个特定的权重。
2. Location：只是一个位置（例如 1）。
3. RouteEngine：此类将计算从给定 startPoint 的所有路径。
4. Route：此类保存有关两点之间路径的信息（使用 RouteEngine 类生成）。

Location

最简单的类。它只保存一个名称以供显示。

Connection

此类包含两个 Location 对象和一个 weight。

public Connection(Location a, Location b, int weight)
{
    this._a = a;
    this._b = b;
    this._weight = weight;
}

路线

此类包含一条路径。它只有连接列表和总权重。此类由路由引擎生成。

路由引擎

这是驱动该组件的类。算法如下

1. 将 startPosition 设置为活动状态
2. 将所有路径的总权重设置为无穷大
3. 迭代活动位置的所有连接，如果它们的权重小于它们的当前权重，则存储它们的权重
4. 将活动位置设置为已使用
5. 将未使用的最近点（在任何位置）设置为活动状态
6. 重复 3、4、5，直到所有位置都被使用

以下方法将执行所有这些步骤（以及一些额外的检查和思考）。返回的 Dictionary 是目的地位置的列表以及到每个目的地位置的相应路径。

/// 

/// Calculates the shortest route to all the other locations
/// 
/// List of all locations and their shortest route
public Dictionary CalculateMinCost(Location _startLocation)
{
    //Initialise a new empty route list
    Dictionary _shortestPaths = new Dictionary();
    //Initialise a new empty handled locations list
    List _handledLocations = new List();

    //Initialise the new routes. the constructor will set the route weight to in.max
    foreach (Location location in _locations)
    {
        _shortestPaths.Add(location, new Route(location.Identifier));
    }

    //The startPosition has a weight 0.
    _shortestPaths[_startLocation].Cost = 0;

    //If all locations are handled, stop the engine and return the result
    while (_handledLocations.Count != _locations.Count)
    {
        //Order the locations
        List _shortestLocations = (List < Location > )(from s in _shortestPaths
                                orderby s.Value.Cost
                                select s.Key).ToList();

        Location _locationToProcess = null;

        //Search for the nearest location that isn't handled
        foreach (Location _location in _shortestLocations)
        {
            if (!_handledLocations.Contains(_location))
            {
                //If the cost equals int.max, there are no more possible connections 
                //to the remaining locations
                if (_shortestPaths[_location].Cost == int.MaxValue)
                    return _shortestPaths;
                _locationToProcess = _location;
                break;
            }
        }

        //Select all connections where the startposition is the location to Process
        var _selectedConnections = from c in _connections
                                   where c.A == _locationToProcess
                                   select c;

        //Iterate through all connections and search for a connection which is shorter
        foreach (Connection conn in _selectedConnections)
        {
            if (_shortestPaths[conn.B].Cost > conn.Weight + _shortestPaths[conn.A].Cost)
            {
                _shortestPaths[conn.B].Connections = 
                        _shortestPaths[conn.A].Connections.ToList();
                _shortestPaths[conn.B].Connections.Add(conn);
                _shortestPaths[conn.B].Cost = conn.Weight + _shortestPaths[conn.A].Cost;
            }
        }
        //Add the location to the list of processed locations
        _handledLocations.Add(_locationToProcess);
    }

    return _shortestPaths;
}

历史

• 2007年12月24日：首次发布