java - 如何使用 bfs 和 java 中的路由表在图中绘制最安全的路由

Question

我有一个包含资源水平的节点图，它们可以是正的也可以是负的，原理是一只雌鸟或一些物体从每个节点获得生命或被一个节点伤害。

我已经设法用队列结构实现 BFS:-

给定一个没有节点资源的图

  a---b---e
  |       |
  c---d   f

路由表是:-

node    parent
===============
a       null
b       a
c       a
d       c
e       b
f       e

因此路线是使用父节点绘制的，假设 (a) 是起始节点，(f) 是导出节点 最快的路线是从底部 f-e-b-a

我在 Java 代码中解决了这个问题，问题是如何在每个节点上使用这个方法，每个节点都有可以杀死你或给你生命的资源。

所以说一些节点有 -20 而其他节点有 +10

鉴于我使用的队列结构，我不确定如何确定路由。

有没有人有什么想法？

我不一定需要 Java 代码，但是任何东西都会有所帮助，我真的对解决方案的理论以及可以使用的数据结构等感兴趣...

我的想法是可能

child  parent  resource
=======================
a       b       20+
b       a       10-
c       b       5+

问题是我不确定如何存储不同的路线，该表只存储一条路线。

Answer 1

当所有边的长度都不相同时，BFS 并不真正用于寻找最短路径。我建议 Bellman Ford Algorithm .与 Dijkstra 算法一样，它用于计算给定图形的最短路径。但是，与 Dijkstra 的算法不同，它允许您对并非所有边长都为正的图形进行操作(看来您已经提出了问题)。

这是一个 video解释它(通过 OpenCourseWare)。