Somehow, my modified BFS is performing better than Dijkstra's?
I want to know what the exact time complexity is of this solution, I have spent a lot of time thinking but my only understanding is that is unbounded. I think it may have complexity O(EV) since worst case would be to iterate through every vertex, each vertex having E/V edges, and each edge resulting in every other vertex needing to be updated. So V * E/V * V = EV.
The idea is that I have a weighted directed graph. I need to find the route from the origin to every other node such that this "shortestPath" route has the highest minimum weight along the way. So if a the route went through weights 1 and 3, it's "score" would be 1 (the minimum), another route that arrived at the same node through edges with weights 2 and 3 would have a "score" of 2 which means it is the better route.
The pseudocode is as follows:
linkedlist queue
array shortestpaths
add origin to queue
while queue is not empty:
current <- pop the item from front of queue
for edge in edges starting at current:
child <- edge.end // edge.start would be current
if minimum(shortestpaths[current], edge.weight) > shortestpaths[child]:
visited[child] = false // Triggers all children to be looked at again
shortestpaths[child] = minimum(shortestpaths[current], edge.weight)
if not visited[child]:
queue.addToBack(child)
visited[child] = true // Registers that it has been added to queue
I have done extensive research, but the only sources I found mentioned that triggering an update to all children in a BFS makes it "unbounded" and worse time complexity than Dijkstras. However, I think in this case due to the fact I am searching for the route with the highest minimum-weighted-edge it passes through, the complexity is different.
After doing simulations with random values all the way up to 300000 nodes and 1000000 edges, this pseudocode performs 2-3 times better than Dijkstra's which is O(ElogV). To give the exact results, it did approximately 700000 operations with the tests, however dijkstra's did around 1.8 million. Which matches its time complexity as well. At small values and even with multiple cycles and edges going both directions, it consistenly performed faster (time-wise) and with less operations than dijkstra's.
I'm thinking it's complexity would either be O(V^2) or O(EV) but am not 100% sure, the part which confuses me is that only some nodes are marked as unseen. And the same node could be marked back to unseen multiple times. Also, neither of those complexities match its growth rate, which is slower than O(ELogV) -> I figured out after graphing points based on E and based on V vs the amount of time taken for program to run and vs the time complexity.