Java求解股票经纪人KK想要在一群人(n个人的编号为0~n-1)中散布一个传言,传言只通过认识的人进行传递,在两个认识的人之间传递消息所需要的时间各有不同,在一群人中,KK想要找出以哪个人为起点开始传递这个传言,可以在耗时最短的情况下认所有人都收到消息。
时间: 2024-01-24 07:20:42 浏览: 15
这是一个经典的图论问题,可以使用 Dijkstra 算法来解决。
首先,我们需要建立一个无向图,其中节点表示人,边表示人与人之间的认识关系,边权表示传递消息所需要的时间。
然后,我们可以从每个节点开始运行 Dijkstra 算法,求出从该节点开始传递消息所需要的最短时间。最终,找到所有节点中最小的最短时间,即可确定起点。
Java 代码实现如下:
阅读全文