Най-кратки пътища между два града

[Гост]

Код: Избери целия код

minS = 1000000; minPath = []
H = [[0, 1, 3, 5],
     [1, 0, 2, 6],
     [3, 2, 0, 2],
     [5, 6, 2, 0]]

bgn = 0; end = 3

def MinPath(a, path, S, b):
    global minS, H
    if a == b:
        if S < minS:
            minS = S
    else:
        for c in range(len(H)):
            if H[a][c] != 0 and not c in path:
                MinPath(c, path + [c], S + H[a][c], b)

def RecoverMins(a, path, S, b):
    global minS, minPath, H
    if a == b:
        if S == minS:
            minPath += [path]
    else:
        for c in range(len(H)):
            if H[a][c] != 0 and not c in path:
                RecoverMins(c, path + [c], S + H[a][c], b)

MinPath(bgn, [bgn], 0, end)
RecoverMins(bgn, [bgn], 0, end)
print((minS, minPath))

Функцията-метод MinPath намира дължината на най-краткия път, а RecoverMins - всички пътища с тази (най-малка) дължина. Дали е възможно двата метода да се обединят?

[peyo]

...Функцията-метод MinPath намира дължината на най-краткия път, а RecoverMins - всички пътища с тази (най-малка) дължина. Дали е възможно двата метода да се обединят?

Yeah!

Код: Избери целия код

minS = 1000000; minPath = []
H = [[0, 1, 3, 5],
     [1, 0, 2, 6],
     [3, 2, 0, 2],
     [5, 6, 2, 0]]

bgn = 0; end = 3

def MinRecPath(a, path, S, b):
    global minS, minPath,H
    if a == b:
        if S < minS:
            minS = S
        if S == minS:
            minPath += [path]
    else:
        for c in range(len(H)):
            if H[a][c] != 0 and not c in path:
                MinRecPath(c, path + [c], S + H[a][c], b)


MinRecPath(bgn, [bgn], 0, end)
print((minS, minPath))

[Гост]

И аз първоначално мислех да го направя така, но в такъв случай операторът minPath += [path] може да се изпълни за някое S, станало равно на minS, когато minS още не е придобило глобална минимална стойност, а само S е повторило минималната стойност от изчислените до текущия момент.

[Гост]

А и още нещо. В тези две проверки:

Код: Избери целия код

        if S < minS:
            minS = S
        if S == minS:
            minPath += [path]

ако първото условие S < minS е изпълнено, minS ще стане равно на S и второто условие S == minS ще бъде винаги изпълнено.

Аз мислех да го направя:

Код: Избери целия код

        if S < minS:
            minS = S
        elif S == minS:
            minPath += [path]

но се отказах поради обясненото в горната публикация.

[Гост]

От друга страна, Peyo, кодът Ви работи. Много благодаря! Сигурно аз не разсъждавам правилно.

[peyo]

От друга страна, Peyo, кодът Ви работи. Много благодаря! Сигурно аз не разсъждавам правилно.

Не, може да има грешка. Примера който имаме не е много добър да я хване. Може да оправим проблема например така.

Код: Избери целия код

def MinRecPath(a, path, S, b):
    global minS, minPath,H
    if a == b:
        if S < minS:
            minS = S
            minPath=[]  # reset the result
        if S == minS:
            minPath += [path]
    else:
        for c in range(len(H)):
            if H[a][c] != 0 and not c in path:
                MinRecPath(c, path + [c], S + H[a][c], b)

[peyo]

Като се замисля повече, не се ли опитваме тук да намерим най-късия път в граф? Текущия алгоритъм е ужасно лош, защото има ако не се лъжа $O(V!)$ сложност. Много по-добре би било да ползваме Дийкстра алгоритъма който e $O(V^2)$.

[Гост]

След добавяне на оператора за изчистване на множеството от минимални пътища всичко работи ОК. Още веднъж благодаря! А по-отношение сложността - наистина е от порядък факториел, понеже структурата на рекурсивността заимствах от алгоритъм за генериране на пермутации. Разбира се, Дейкстра е по-бърз.

[Гост]

Лошото е, че алгоритъмът на Дейкстра, който намерих:

Код: Избери целия код

namespace Dijkstra
{
    internal class Program
    {
        class Dijkstra
        {
            private int[,] mapMatrix;
            private int[] distance;
            private int[] visitedNodes;
            public Dijkstra()
            {
                this.mapMatrix = new int[,]
                {
               {0, 2, 4, 6},
               {2, 0, 2, 4},
               {4, 2, 0, 2},
               {6, 4, 2, 0}
                };
                this.distance = new int[this.mapMatrix.GetLength(0)];
                this.visitedNodes = new int[this.mapMatrix.GetLength(0)];
            }
            public void DijikstraAlgorithm()
            {
                for (int i = 0; i < this.distance.Length; i++)
                {
                    if (this.mapMatrix[0, i] == 0)
                    {
                        this.distance[i] = int.MaxValue;
                    }
                    else
                    {
                        this.distance[i] = this.mapMatrix[0, i];
                    }
                    this.visitedNodes[i] = i;
                }
                this.visitedNodes[0] = -1;
                for (int j = 0; j < this.distance.Length / 2; j++)
                {
                    int currentShortestWay = int.MaxValue;
                    int nextNodeOnShortestWay = 0;
                    for (int i = 0; i < this.distance.Length; i++)
                    {
                        if ((this.distance[i] < currentShortestWay) && (this.visitedNodes[i] != -1))
                        {
                            currentShortestWay = this.distance[i];
                            nextNodeOnShortestWay = i;
                        }
                    }
                    for (int i = 0; i < this.distance.Length; i++)
                    {
                        if (this.visitedNodes[i] != -1)
                        {
                            if (this.mapMatrix[nextNodeOnShortestWay, i] != 0)
                            {
                                if (this.distance[i] > this.distance[nextNodeOnShortestWay] +
                                        this.mapMatrix[nextNodeOnShortestWay, i])
                                {
                                    int newDistance = this.distance[nextNodeOnShortestWay] +
                                        this.mapMatrix[nextNodeOnShortestWay, i];
                                    this.distance[i] = newDistance;
                                }
                            }
                        }
                    }
                    this.visitedNodes[nextNodeOnShortestWay] = -1;
                }
            }           
            public void PrintShortestWays()
            {
                for (int i = 0; i < this.distance.Length; i++)
                {
                    if (this.distance[i] == int.MaxValue)
                    {
                        Console.WriteLine("The shortest way to node: {0}, is – \"start point\"", i + 1);
                    }
                    else
                    {
                        Console.WriteLine("The shortest way to node: {0}, is – {1}",
                            i + 1, this.distance[i]);
                    }
                }
            }
        }
        static void Main(string[] args)
        {
            Dijkstra test = new Dijkstra();
            test.DijikstraAlgorithm();
            test.PrintShortestWays();
        }
    }
}


намира само дължината на ной-кратките пътища от даден град до всички останали, но не и самите пътища по градове, през които се минава. А ако ще се прави меморизация на най-кратките пътища, по-лесен ми се струва записът на Python в сравнение със C#.

[Гост]

Намерих и на Python, но също се извеждат само най-кратките разстояния до всеки град, а не и градовете, през които се минава:

Код: Избери целия код

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

    def printSolution(self, dist):
        print("Vertex \t Distance from Source")
        for node in range(self.V):
            print(node, "\t\t", dist[node])

    def minDistance(self, dist, sptSet):
        min_dist = float("inf")
        min_index = -1
        for v in range(self.V):
            if dist[v] < min_dist and not sptSet[v]:
                min_dist = dist[v]
                min_index = v
        return min_index

    def dijkstra(self, src):
        dist = [float("inf")] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for _ in range(self.V):
            u = self.minDistance(dist, sptSet)
            sptSet[u] = True

            for v in range(self.V):
                if (
                    self.graph[u][v] > 0
                    and not sptSet[v]
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)

# Example usage
g = Graph(9)
g.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0],
]

g.dijkstra(0)