Пример алгоритма Дейкстры, когда источник и пункт назначения совпадают

Question

Учитывая следующий Направленный взвешенный график, как можно найти кратчайший маршрут, который начинается и заканчивается в B?

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

Вот мой код, пока что

public static int ShortestDistance(Graph graph, Node from, Node to)
{
    var distances = new Dictionary<Node, int>();
    var actualNodes = graph.GetNodes() as List<Node> ?? Graph.GetNodes().ToList();

    foreach (var node in actualNodes) distances[node] = node.Equals(from) ? 0 : int.MaxValue;

    while (actualNodes.Count() != 0)
    {
        var actualShortest = actualNodes.OrderBy(n => distances[n]).First();
        actualNodes.Remove(actualShortest);

        if (distances[actualShortest] == int.MaxValue) break;

        if (actualShortest.Equals(to)) return distances[actualShortest];

        foreach (var adjacent in graph.GetAdjacentsByNode(actualShortest))
        {
            var actualDistance = distances[actualShortest] + adjacent.Weight;
            if (actualDistance >= distances[adjacent.To]) continue;
            distances[adjacent.To] = actualDistance;
        }
    }

    throw new Exception($"There's no such route from '{from}' to '{to}'.");
}

Answer 1

Каноническим способом сделать это будет дублирование (или «тень») узла B (назовите его BB) с одинаковыми входящими и исходящими ребрами и весами.

Теперь применитеАлгоритм Дейкстры, чтобы найти кратчайший путь от B до BB.У вас уже есть этот код (т. Е. «Мы теперь свели проблему к чему-то, что было ранее решено»).

Answer 2

Разделить узел на два узла:

• узел S сохраняет все исходящие ребра
• узел D сохраняет все входящие ребра

Теперь решите обычно для S как источник и D как пункт назначения.

Answer 3

Если разрешен маршрут нулевой длины:

• Тогда ответ просто 0.

Если под маршрутом вы подразумеваете путь длиной> 0:

• Запустите Dijkstra из исходного кода, получите массив sp [], такой, чтобы sp [x] сохранял кратчайший путь от источника к x (это обычное использование Dijkstra)

• Теперь рассмотрим все ребра, входящие в источник.

• Скажем, ребро это x -> источник с весом w

• Таким образом, мы можем достичь источника с длиной пути> 0 с общим весом sp [x] + w

• Из всех таких маршрутов выберите минимум один.

Answer 4

Ваша реализация этого алгоритма очень медленная, но он работает. Если вы хотите найти путь> 0 от узла к себе, вы можете просто изменить свою инициализацию следующим образом:

public static int ShortestDistance(Graph graph, Node from, Node to)
{
    var distances = new Dictionary<Node, int>();
    var actualNodes = graph.GetNodes() as List<Node> ?? Graph.GetNodes().ToList();

    foreach (var node in actualNodes) distances[node] = int.MaxValue;

    foreach (var adjacent in graph.GetAdjacentsByNode(from))
    {
        distances[adjacent.To] = adjacent.Weight;
    }

    while (actualNodes.Count() != 0)
    {
        var actualShortest = actualNodes.OrderBy(n => distances[n]).First();
        actualNodes.Remove(actualShortest);

        if (distances[actualShortest] == int.MaxValue) break;

        if (actualShortest.Equals(to)) return distances[actualShortest];

        foreach (var adjacent in graph.GetAdjacentsByNode(actualShortest))
        {
            var actualDistance = distances[actualShortest] + adjacent.Weight;
            if (actualDistance >= distances[adjacent.To]) continue;
            distances[adjacent.To] = actualDistance;
        }
    }

    throw new Exception($"There's no such route from '{from}' to '{to}'.");
}