我正在尝试使用广度优先搜索算法找到两个给定城市之间的最短路径 . 然后我希望能够打印出那条路 . 我有一个存储在多维数组中的城市矩阵(数组[8] [8]) . 矩阵看起来像这样:
#1 #2 #3 #4 #5 #6 #7 #8
#1 0 100 -1 10 -1 -1 -1 100
#2 100 0 -1 -1 10 10 -1 -1
#3 -1 -1 0 1000 100 -1 1000 -1
#4 50 -1 720 -1 -1 -1 -1 -1
#5 -1 10 100 -1 0 -1 100 -1
#6 -1 10 -1 -1 -1 0 50 2000
#7 -1 -1 1000 -1 100 10 0 -1
#8 100 -1 -1 -1 -1 1000 -1 0
如果数字大于0则表示这两个城市之间有一条路径 . 例如,城市#2具有到城市#1的路径,因为它具有数字100.我需要找到从给定源城市到目的地城市的最短路线 .
我的问题是,是否可以修改广度优先搜索算法在矩阵上执行此操作,还是应该将数据存储在另一个数据结构中?
1 回答
您需要使用
Node
类,该类具有当前节点的属性,而不仅仅是原始节点 . 因此,当您找到连接到当前节点的所有节点时,您将为子节点创建一个新对象,并将parent
属性设置为当前节点 .然后,一旦找到最短路径,就会遍历父属性,直到到达根(具有空父级) .
这是简单的解释(我说“节点”足够多了吗?)...希望它有意义 .