A variant of Dijkstra’s to choose optimal source between all nodes

graph theory

I have a question about graph theory, which I am not very well versed in.

Currently:
I am using Dijkstra's algorithm to find the optimal path from a single source to all other nodes.
My network is non-directional and each edge has a value between [0, 1].
The value given to each node is the value of the worst edge (lowest value) on the best path (highest value).

I have added a simple Image here:
Simple Dijkstra
Where the source is blue, the edge values are black, the node values are red, and the edges used by the algorithm are also red.

My problem:
If I choose a bad node (one with only low value edges connected to it), all the other nodes will be defined by those first edges, and they will have very low values.

I got the idea of trying to optimize my results by choosing the best source, the source that optimizes eg. the average or median value of all nodes.

I tried to brute force it in a for loop where I looped over all the nodes as sources, which is gonna take a while, I have 50000 nodes, and 200000 edges.
Which, with my own implementation of Dijkstra, is gonna take several days

I have looked on the internet for similar algorithms but have not found any that seemed suitable.

My question is, does such an algorithm exist, or do I just have to brute force it?

Best Regards,
Jakob

Best Answer

I think you may have a look at Prim's algorithm. Basically, it grows a tree step by step by starting from no edge selected to a subtree of your graph, and at each step it select the edge with higher value to put in the tree. This is how it goes:

  1. Sort the edge set $E$ in decreasing order. (will be very useful in step 3)
  2. For each node $s$: let $S = \{s\}$ be the set of reached nodes
  3. While $S \ne V$, pick the edge $ab$ of highest value such that $a\in S$ and $b \in V-S$. Then you grow the reached nodes $S = S + \{b\}$.
  4. compute the metric you are interested in, and go back to step 2.

The step 3 can be donne quite efficiently using appropriate data structures. (fibonnacci heaps etc.)

Related Question