SQL Server实现短路径的搜索算法
作者:网络转载 发布时间:[ 2013/4/25 10:58:46 ] 推荐标签:
这是去年的问题了,在整理邮件的时候才发现这个问题,感觉顶有意思的,特记录下来。

图1
解析
为了能够更好的描述表RelationGraph中字段Node和 RelatedNode的关系,我在这里特意使用一个图形来描述,如图2

图2
在图2,可清晰的看出各个节点直接如何相连,也可以清楚的看出节点"p"至节点"j"的的几种可能路径。

从上面可以看出第2种可能路径,经过的节点少。
为了解决开始的问题,我参考了两种方法:
第1方法是:参考单源短路径算法:Dijkstra(迪杰斯特拉)算法,主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

图3
本文内容不用于商业目的,如涉及知识产权问题,请权利人联系SPASVO小编(021-61079698-8054),我们将立即处理,马上删除。

sales@spasvo.com