Параметры алгоритма кратчайшего пути c #

Question

Я пытаюсь понять, как реализовать алгоритм кратчайшего пути.Я не уверен, что является наиболее подходящим и мог бы использовать некоторые рекомендации, как мне поступить.

У меня есть список линий, которые составляют мою сеть.Линия состоит из 2 или более точек широты / долготы (LatLng).т.е. IEnumerable<LatLng[]> networkLines.

Вот пример того, как моя линейная сеть может выглядеть графически.Допустим, две линии красного цвета находятся вне начальной и конечной точек.Маленькие черные линии являются примерами того, где линии могут начинаться и заканчиваться, каждая из которых может иметь несколько точек между этим графиком вдоль его курса.

Любой совет, как мне поступить, был бы поразителен?

Я попытался реализовать способ расчета, соединены ли линии, так как есть вероятность, что они могут и не быть.Я не уверен, поможет ли это, но я включу ниже для контекста.

// Number of steps or iterations
var numberOfSteps = 1;

// Lines connected to SiteLogger1
var connectedLines =
    lineNetworkCoordinates.Where(line => line.Any(coord => sourceLine.Any(x => x.Latitude == coord.Latitude && x.Longitude == coord.Longitude))
    && line != sourceLine);

// Keep a track of lines that have been spanned
List<LatLng[]> previouslySpannedLines = connectedLines.ToList();

// Iterate over network for number of steps set
while (numberOfSteps < maxNumberOfSteps)
{
    // Set the current connected lines to not be any that are in the previously spanned collection 
    // and also have lat/lng that meet one of the new collections
    connectedLines =
        lineNetworkCoordinates.Where(line => !previouslySpannedLines.Contains(line, new LatLngArrayComparer())
        && line.Any(coord => previouslySpannedLines.SelectMany(x => x).Any(x => x.Latitude == coord.Latitude && x.Longitude == coord.Longitude)));

    // If the SiteLogger2's line exists in collection then it's successful
    if (connectedLines.Contains(destinationLine, new LatLngArrayComparer()))
    {
        return true;
    }

    previouslySpannedLines.AddRange(connectedLines);
    numberOfSteps++;
}

return false;

РЕШЕНИЕ:

Решение было найдено с использованием небольшой модификации https://gist.github.com/keithcollins/307c3335308fea62db2731265ab44c06

Для дальнейшего использования, это код, который я изменил, чтобы работать для того, что мне нужно:

public class PriorityQueue<T>
{
    // From Red Blob: I'm using an unsorted array for this example, but ideally this
    // would be a binary heap. Find a binary heap class:
    // * https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/wiki/Home
    // * http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
    // * http://xfleury.github.io/graphsearch.html
    // * http://stackoverflow.com/questions/102398/priority-queue-in-net

    private List<KeyValuePair<T, float>> elements = new List<KeyValuePair<T, float>>();

    public int Count
    {
        get { return elements.Count; }
    }

    public void Enqueue(T item, float priority)
    {
        elements.Add(new KeyValuePair<T, float>(item, priority));
    }

    // Returns the Location that has the lowest priority
    public T Dequeue()
    {
        int bestIndex = 0;

        for (int i = 0; i < elements.Count; i++)
        {
            if (elements[i].Value < elements[bestIndex].Value)
            {
                bestIndex = i;
            }
        }

        T bestItem = elements[bestIndex].Key;
        elements.RemoveAt(bestIndex);
        return bestItem;
    }
}

public class AStarSearch
{
    // Someone suggested making this a 2d field.
    // That will be worth looking at if you run into performance issues.
    public Dictionary<LatLng[], LatLng[]> cameFrom = new Dictionary<LatLng[], LatLng[]>();
    public Dictionary<LatLng[], float> costSoFar = new Dictionary<LatLng[], float>();

    private LatLng[] start;
    private LatLng[] goal;

    static public float Heuristic(LatLng[] a, LatLng[] b)
    {
        return MapCoordinate.FindLineDistance(a) + MapCoordinate.FindLineDistance(b);
    }

    // Conduct the A* search
    public AStarSearch(IEnumerable<LatLng[]> graph, LatLng[] start, LatLng[] goal)
    {
        // start is current sprite Location
        this.start = start;
        // goal is sprite destination eg tile user clicked on
        this.goal = goal;

        // add the cross product of the start to goal and tile to goal vectors
        // Vector3 startToGoalV = Vector3.Cross(start.vector3,goal.vector3);
        // Location startToGoal = new Location(startToGoalV);
        // Vector3 neighborToGoalV = Vector3.Cross(neighbor.vector3,goal.vector3);

        // frontier is a List of key-value pairs:
        // Location, (float) priority
        var frontier = new PriorityQueue<LatLng[]>();

        // Add the starting location to the frontier with a priority of 0
        frontier.Enqueue(start, 0f);

        cameFrom.Add(start, start); // is set to start, None in example
        costSoFar.Add(start, 0f);

        while (frontier.Count > 0f)
        {
            // Get the Location from the frontier that has the lowest
            // priority, then remove that Location from the frontier
            LatLng[] current = frontier.Dequeue();

            // If we're at the goal Location, stop looking.
            if (current.Equals(goal)) break;

            // Neighbors will return a List of valid tile Locations
            // that are next to, diagonal to, above or below current
            foreach (var neighbor in graph.Where(line => line.Any(coord => current.Any(x => x.Latitude == coord.Latitude && x.Longitude == coord.Longitude))
                && line != current).ToList())
            {

                // If neighbor is diagonal to current, graph.Cost(current,neighbor)
                // will return Sqrt(2). Otherwise it will return only the cost of
                // the neighbor, which depends on its type, as set in the TileType enum.
                // So if this is a normal floor tile (1) and it's neighbor is an
                // adjacent (not diagonal) floor tile (1), newCost will be 2,
                // or if the neighbor is diagonal, 1+Sqrt(2). And that will be the
                // value assigned to costSoFar[neighbor] below.
                float newCost = costSoFar[current] + MapCoordinate.FindLineDistance(neighbor);

                // If there's no cost assigned to the neighbor yet, or if the new
                // cost is lower than the assigned one, add newCost for this neighbor
                if (!costSoFar.ContainsKey(neighbor) || newCost < costSoFar[neighbor])
                {

                    // If we're replacing the previous cost, remove it
                    if (costSoFar.ContainsKey(neighbor))
                    {
                        costSoFar.Remove(neighbor);
                        cameFrom.Remove(neighbor);
                    }

                    costSoFar.Add(neighbor, newCost);
                    cameFrom.Add(neighbor, current);
                    float priority = newCost + Heuristic(neighbor, goal);
                    frontier.Enqueue(neighbor, priority);
                }
            }
        }

    }

    // Return a List of Locations representing the found path
    public List<LatLng[]> FindPath()
    {

        List<LatLng[]> path = new List<LatLng[]>();
        LatLng[] current = goal;
        // path.Add(current);

        while (!current.Equals(start))
        {
            if (!cameFrom.ContainsKey(current))
            {
                //MonoBehaviour.print("cameFrom does not contain current.");
                return new List<LatLng[]>();
            }
            path.Add(current);
            current = cameFrom[current];
        }
        // path.Add(start);
        path.Reverse();
        return path;
    }