New answers tagged

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 ...
user avatar
  • 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 ...
user avatar
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$.
user avatar
  • 1,188

Top 50 recent answers are included