我的任务是(课程作业@大学)实施一种寻路方式.现在,在规范中,我可以实现一个蛮力,因为搜索节点的数量有限(开始,中间两个,结束),但我想重新使用这个代码来实现Dijkstra的算法.
我已经在维基百科上看过伪,一位朋友也为我写了一些,但它没有意义.这个算法看起来非常简单,对我来说理解它并不是一个问题,但我不能为我的生活可视化实现这种事情的代码.
有什么建议/提示吗？
编辑一些混淆:
是的,有一个目标节点和一个源节点.
我想在一般情况下实现Dijkstra,而不是"只有两个中间停止"的情况,因为我想在之后再次使用代码.另外,我只是写一个暴力实施.
我遇到一些麻烦的具体问题是存储次优的半成形路径,以防它们变得最佳.当我访问给定节点时,我只是看不到我将如何更新通过它的所有连接.
更多编辑:
现在完成几个答案,然后继续.
真正的编辑:我忘了提到一个严重的并发症,即任何两个顶点之间可以有不同的UINT_MAX距离.抱歉.事实上,我忘了处理这个问题的事实可能首先是该死的问题的原因,尽管解决方案:对我来说,选择最短的问题是显而易见的.难怪其他人对于距离变量的伪没有考虑到我的可变距离.
这是Dijkstra算法的高级细分:
您将所有顶点都放在优先级队列中,其中所有顶点的优先级(距离)都是无穷大,除了源顶点,其距离为零(源顶点距离自身的距离为零,对吗？ ).
弹出优先级队列.删除的顶点是距离源最短距离的顶点.显然,从队列中弹出的第一个顶点是源.好吧,调用popped顶点v.
看看v的每个邻居.所有这些距离都大于v的距离(否则我们就已经从队列中弹出它们了,对吧？).假设v的距离为3,v有3个邻居x(dist-from-source:5),y(dist-from-source:10)和z(dist-from-source:infinity).
现在我们来看看每个邻居与v的距离.假设它们是:x - 3,y - 2,z - 4.这意味着从源到x经过v的路径的距离为| v | + 3(3 + 3 = 6),y的距离为5(3 + 2 = 5),z的距离为7(3 + 4 = 7).
x到v的路径比当前到x的最短路径要长,所以我们忽略它.但是,通过v的y和z的路径比先前已知的最短路径短,因此我们更新它们.
你一直这样做,直到你经历了所有的顶点.在每个点,当您从优先级队列中弹出min时,您知道已找到到该顶点的最短路径,因为任何可能的较短路径必须通过距离小于v的顶点,这意味着我们已经弹出从队列中.