Suppose we have a variant of Dijkstra's algorithm which uses just a simple queue, doesn't mark vertices as "done" and thus any vertex can be updated any number of times like in the following python code:
"""
here Graph is an adjacency list implemented by dictionaries
"""
from collections import deque
def dijkstra(graph: Graph, start: str) -> Dict[str, float]:
queue = deque()
shortest_distances = dict()
shortest_distances[start] = 0
queue.append(start)
while queue:
vertex = queue.popleft()
for neightbour in graph[vertex]:
edge_weight = graph[vertex][neightbour]
parent_weight = shortest_distances[vertex]
existing_weight = shortest_distances.get(neightbour, float('inf'))
if existing_weight == float('inf') or \
parent_weight + edge_weight < existing_weight:
shortest_distances[neightbour] = parent_weight + edge_weight
queue.append(neightbour)
return shortest_distances
Obviously this version of the algorithm works with negative weights in the absence of negative cycles.
Here are some doubts i have about it 1.) What is the worst-case performance when only non negative weights are present, and why? 2.) What is the worst-case performance when negative weights but not negative cycles are present, and why? 3.) Are the two above different, and if yes then why? 4.) Is the performance of the above variant better/worse/alike of that of similar algorithms like Bellman-Ford or Floyd-Warshall
My intuition is that with only positive weights the variant is O(N^2) like other simple variants of Dijkstra's algorithm, but I’m not sure how to prove it. I also suspect that with negative weights there could be cases of exponential performance but I wasn’t able to find a concrete example.