Looks like I came up with my own algorithm for finding the shortest path

Hi all! I seem to have implemented my own algorithm for finding the shortest path with negative graph edges.

Why your own? I was looking for a similar solution, but I didn’t find it, perhaps it was already implemented, I just didn’t search well. I'm waiting for the Nobel Prize =)

I came up with it by modifying Dijkstra's classic. I ask you to take an adequate approach to the content, because this is my first article, and perhaps I did not invent anything and, in general, this algorithm does not work at all (but according to my tests, it works correctly).

I repeat, the algorithm works with negative edges of the graph (but not with cyclic negatives). How does this algorithm differ from the famous Bellman-Ford

Complexity! The known algorithm has a complexity of O(n³). According to my calculations, “my” algorithm has a complexity that does not exceed the original complexity of Dijkstra’s algorithm, namely O(n²). If this is not so, please correct it after familiarizing yourself with the implementation in the language Python

Implementation

So we have a graph with a negative edge between the 2nd and 5th node. Our task is to find the shortest path from the source (1st node) to the 9th node.

The graph will be stored as a hash table, where:

graph = {
node_1_(source): {neighbor_1: weight before it, neighbor_2: weight before it, …},
node_2: {neighbor_1: weight before it, neighbor_2: weight before it, …},
…
}

graph = {
    1: {2: 10, 3: 6, 4: 8},
    2: {7: 11, 4: 5, 5: -4},
    3: {5: 3},
    4: {7: 12, 3: 2, 5: 5, 6: 7},
    5: {6: 9, 9: 12},
    6: {8: 8, 9: 10},
    7: {6: 4, 8: 6, 9: 16},
    8: {9: 15},
    9: {}
}

Important! You need to write the graph nodes in order of their distance from the source. Those. First we describe the first neighbors of the source. After we have described them, we move on to the next neighbors of neighbors. Those. We describe it level-by-level, as if it were not a weighted graph, but an ordinary tree, where we implement breadth-first search. In Python, dictionaries are ordered (since version 3.6), so we don't need to resort to other data structures like Ordered dict from module collections.
You can describe the graph with an adjacency matrix, but this is easier for me.

We also need 2 more hash tables.
Minimum weights from the source to this node in the form:
costs = {
node_1_(source): 0,
node_2: infinity,
node_3: infinity,
…
}
We will fill it out and update it as we go through the “children” of nodes.

costs = {}  # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)

Table of parent nodes from which the shortest path to this node passes:

parents = {}  # {Нода: его родитель}

We will also fill it out and update it as we move through the children’s nodes.

As in Dijkstra’s algorithm, we will mark still unknown distances to nodes as infinity. Let's initialize this variable:

infinity = float('inf')  # Бесконечность (когда минимальный вес до ноды еще неизвестен)

Next, we create an empty set. The processed nodes will be stored there (I’ll explain what “processed” means later, but for now we’ll just create a set)

processed = set()  # Множество обработанных нод

Let's get down to the algorithm itself!

We start from the source (the first node). We look at the weights of all its neighbors in the table costs. The path to them is infinite, and any number is already less than infinity, so we update the weights. We also add the parents of all nodes, because we found a shorter path to the node. When we have looked at all the neighbors, we add our node in question to the set of processed nodes processed (we will not process this node further).
This is an important point and difference from Dijkstra's algorithm. We won't watch minimum weight raw knot, but look at all ALL neighbors one by one. Those. we have neighbors after the first stage of the algorithm.
We will also look for their neighbors one by one and update the minimum weights. If the achievable weight turns out to be less than that entered in the table, then we replace it. We also replace its parent in the table parents.
When we have looked at all the neighbors, we add the node to the set of processed ones. Those. many processed – these are the nodes for which we have considered all of its neighbors!
And so we repeat level by level (we don’t proceed to neighbors of neighbors until we process the first neighbors) until all nodes are processed.
Code:

graph = {
    1: {2: 10, 3: 6, 4: 8},
    2: {7: 11, 4: 5, 5: -4},
    3: {5: 3},
    4: {7: 12, 3: 2, 5: 5, 6: 7},
    5: {6: 9, 9: 12},
    6: {8: 8, 9: 10},
    7: {6: 4, 8: 6, 9: 16},
    8: {9: 15},
    9: {}
}

parents = {}  # {Нода: его родитель}
costs = {}  # Минимальный вес для перехода к этой ноде (кратчайшие длины пути до ноды от начального узла)
infinity = float('inf')  # Бесконечность (когда минимальный вес до ноды еще неизвестен)

processed = set()  # Множество обработанных нод
for node in graph.keys():
    if node not in processed:  # Если нода уже обработана не будем ее заново смотреть (иначе м.б. беск. цикл)
        for child, cost in graph[node].items():  # Проходимся по всем детям
            new_cost = cost + costs.get(node,
                                        0)  # Путь до ребенка = путь родителя + вес до ребенка (если родителя нет, то путь до него = 0)
            min_cost = costs.get(child,
                                 infinity)  # Смотрим на минимальный путь до ребенка (если его до этого не было, то он беск.)
            if new_cost < min_cost:  # Если новый путь будет меньше минимального пути до этого,
                costs[child] = new_cost  # то заменяем минимальный путь на вычисленный
                parents[child] = node  # Так же заменяем родителя, от которого достигается мин путь
        processed.add(node)  # Когда все дети (ребра графа) обработаны, вносим ноду в множество обработанных

print(f'Минимальные стоимости от источника до ноды: {costs}')
print(f'Родители нод, от которых исходит кратчайший путь до этой ноды: {parents}')

# -> Минимальные стоимости от источника до ноды: {2: 10, 3: 6, 4: 8, 7: 20, 5: 6, 6: 15, 9: 18, 8: 23}
# -> Родители нод, от которых исходит кратчайший путь до этой ноды: {2: 1, 3: 1, 4: 1, 7: 4, 5: 2, 6: 4, 9: 5, 8: 6}

We obtained the shortest distances from the source to each reachable node in the graph, as well as the parents of these nodes. How can we build a chain of the path we are interested in from the source to the 9th node (or to any other accessible one)? The answer is in the code below:

def get_shortest_path(start, end):
    '''
    Проходится по родителям, начиная с конечного пути,
    т.е. ищет родителя конечного пути, потом родителя родителя и т.д. пока не дойдет до начального пути.
    Тем самым мы строим обратную цепочку нод, которую мы инвертируем в конце, чтобы получить
    истинный кратчайший путь
    '''
    parent = parents[end]
    result = [end]
    while parent != start:
        result.append(parent)
        parent = parents[parent]
    result.append(start)
    result.reverse()
    result = map(str, result)  # В случае если имена нод будут числами, а не строками (для дальнейшего join)
    print(f'Кратчайший путь от {start} до {end}:  {costs[end]}')
    return result


shortest_path = get_shortest_path(start=1, end=9)
print('-->'.join(shortest_path))

# -> Кратчайший путь от 1 до 9:  18
# -> 1-->2-->5-->9

So we've found the shortest path to node 9, and notice it goes through an edge with negative weight! Those. We are no longer afraid of the presence of such an edge, unlike the original Dijkstra.

Complexity

In Dijkstra's original algorithm, the worst-case complexity is

Walk through all nodes of the graph (n)
This cycle contains another one – searching for the minimum unvisited node. It runs in O(n), but can be done in O(Elogn) by implementing a heapq
Traversing node neighbors. Takes O(E), where E is the number of edges in the graph. Because is a constant, then it is omitted.

In total, the algorithm takes O(n²+E), and with the implementation of the heap, the speed increases to O(Elogn) (actually this won't always be the case, but most of the time)

As for “my” algorithm, if I’m not mistaken somewhere:

Traversing all nodes of a graph O(n)
Walking through all neighbors O(n)
Updating weights O(1)

Total O(n²). Not bad! What from memory? costs – O(n), parents – O(n), processed – O(n)
I think it's not bad for this kind of algorithm.

Another detail. When implementing the classic Dijkstra, in the case where the search for the MINIMUM weight node matches our final target node,
then we can interrupt further processing, because we have already found the shortest path to the node of interest. In “my” algorithm, we will still process all nodes.

conclusions

If we may encounter negative edges in the graph, we can use this algorithm. You can also use the famous Bellman-Ford, as you like, but I found it more difficult to understand.
If we know that the graph does not contain negative weights, then we can safely use Dijkstra.

I EMPHASIZE AGAIN!

I don't know if this algorithm existed before or not. It may not work correctly at all, but I tested it with different data and it worked correctly.

If there are any amendments or comments, I am waiting for feedback. Maybe the implementation generally only works with certain graphs, perhaps there are some that will break everything 🙂

Thank you everyone, I look forward to your opinion on this article!