New answers tagged weighted-graphs
0
votes
Algorithms for finding closest graph node within set of nodes
Without the addendum, you could do $O(|V|+|E|)$-time preprocessing (a single BFS, starting from the set $N$) that would let you solve each query in $O(1)$ time.
With the addendum, this seems much ...
D.W.♦
- 143k
0
votes
Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?
One solution would be to convert the original graph to a graph with only edge costs, and then use Dijkstra's algorithm.
To do this we can replace a single node with n nodes which are fully connected ...
3
votes
Accepted
Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
Yes, MSTs usually don't contain the shortest path for any pair of nodes. The simplest example is probably just the MST of 3 nodes connected to each other all with edge weight $1$.
- 1,188
Top 50 recent answers are included