What problem is this: Cost of the path is the minimum cost of one edge

Правка en4, от peacebringer167, 2022-09-09 18:50:27

In an undirected graph, we define that the cost of a path is the minimum value of AN EDGE that lies in the path. For example, there is a path like this: 1->2->4, and the weight of the edge between (1,2),(2,4) are 9 and 13 consecutively, so the cost of this path is 9. Consider the cost of two vertices (u,v), in every path that connects u and v, choose the path that has the highest cost, and that cost is the cost of (u,v).
For example, we have this graph:
https://ibb.co/tmg1xkN
The cost of 1 and 4 is 10, there are 2 paths, 1->2->4 (cost 10) and 1->3->4 (cost 5) so the cost is 10 Given an undirected graph, find the cost between 1 and all other vertices from 2 to N, with N <= 10^5, and the number of edges is smaller than 5.10^6

Can anyone please help me with this? What type of problem is this? Many thanks in advance!!! (Also, pardon me because of my bad English)

Теги graph, ask

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский peacebringer167 2022-09-09 18:50:27 180
en3 Английский peacebringer167 2022-09-09 18:44:48 43 Tiny change: 's graph:<be> \n![ ](h' -> 's graph:<br> \n![ ](h'
en2 Английский peacebringer167 2022-09-09 18:41:42 101
en1 Английский peacebringer167 2022-09-09 18:40:27 888 Initial revision (published)