1

我有一个包含资源级别的节点图，它们可以是正数和负数，原则是一只瓢虫或某些物体从每个节点获得生命或被节点伤害。

我设法用队列结构实现了 BFS：-

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

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

路由表是：-

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

所以路线是使用父节点绘制的，假设（a）是起始节点，（f）是出口节点，最快的路线是从底部 feba

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

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

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

有没有人有任何想法？

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

我的想法是

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

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

4

1 回答 1

0

当所有边长都不相同时，BFS 并没有真正用于寻找最短路径。我建议使用Bellman Ford 算法。与 Dijkstra 算法一样，它用于计算给定图的最短路径。但是，与 Dijkstra 的算法不同，它允许您对并非所有边长都是正数的图进行操作（看起来您会提出问题）。

这是一个解释它的视频（通过 OpenCourseWare）。

于 2012-04-22T16:37:00.913 回答