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$.
Top 50 recent answers are included
Related Tags
weighted-graphs × 332graphs × 261
algorithms × 156
shortest-path × 74
minimum-spanning-tree × 41
graph-traversal × 32
optimization × 21
spanning-trees × 13
complexity-theory × 12
bipartite-matching × 10
dag × 10
dynamic-programming × 8
dijkstras-algorithm × 8
time-complexity × 7
trees × 7
network-flow × 7
matching × 7
algorithm-analysis × 6
np-complete × 6
correctness-proof × 6
data-structures × 5
colorings × 5
terminology × 4
combinatorics × 4
discrete-mathematics × 4