Ric*_*ral 8 c algorithm graph dijkstra
这个项目的截止日期很快就会结束,我没有太多时间来处理剩下的事情.因此,我正在寻找最简单的算法来实现Graph结构上的一些操作,而不是寻找最好的(可能更复杂/耗时)算法.
我需要做的操作如下:
关于我的Graph实现的一些注意事项:
char,另一个是属性int.它们分别代表关系和重量的类型.我知道我需要做什么:
在给定距离X的情况下列出图形网络中的所有用户
离X什么距离？从起始节点或X他们自己之间的距离？你能给我举个例子吗？这可能或可能不像进行BF搜索或运行Dijkstra那么简单.
假设您从某个节点开始并希望列出距X起始节点有距离的所有节点,只需从起始节点运行BFS即可.当您要在队列中插入新节点时,检查从起始节点到要插入新节点的节点的距离是否是从要插入新节点的节点的边缘权重到新节点是<= X.如果它严格降低,则插入新节点,如果它相等,则只打印新节点(如果您还可以将0作为边缘权重,则仅插入它).
给定距离X和关系类型,列出图形网络中的所有用户
往上看.只考虑与BFS的关系类型:如果父类型与您尝试插入队列的节点的类型不同,请不要插入它.
在给定一种关系的情况下,计算图形网络上2个用户之间的最短路径
该算法取决于许多因素:
既然你想要轻松,最简单的是Roy-Floyd和Dijkstra's.
以下是C实现:Roy-Floyd和Dijkstra_1,Dijkstra_2.你可以在google上找到很多"<algorithm name> c implementation".
编辑:对于18000个节点,Roy-Floyd是不可能的,因为它是一个邻接矩阵.构建和占用太多内存需要花费太多时间.您最好的选择是为每个查询使用Dijkstra算法,但最好使用堆实现Dijkstra - 在我提供的链接中,使用堆来查找最小值.如果您在每个查询上运行经典Dijkstra,那也可能需要很长时间.
另一个选择是在每个查询上使用Bellman-Ford算法,这将为每个查询提供O(Nodes*Edges)运行时.但是,如果你没有像维基百科告诉你的那样实现它,这是一个很大的高估.而是使用类似于BFS中使用的队列.每当节点更新其与源的距离时,将该节点插回队列.这在实践中将非常快,并且也适用于负权重.我建议你使用这个或Dijkstra与堆,因为经典的Dijkstra可能需要很长时间在18 000个节点上.
计算图形网络上2个用户之间的最大距离
最简单的方法是使用回溯:尝试所有可能性并保持找到的最长路径.这是NP完全的,因此不存在多项式解.
如果你有18 000个节点,这真的很糟糕,我不知道任何算法(简单的或其他的)对于这么多节点来说会合理地快速运行.考虑使用贪心算法逼近它.或者您的图表可能具有某些属性,您可以利用这些属性.例如,它是DAG(有向无环图)吗？
计算图形网络上最远的连接用户
意思是你想找到图的直径.最简单的方法是找到每两个节点之间的距离(所有对最短路径 - 在每两个节点之间运行Roy-Floyd或Dijkstra,并选择具有最大距离的两个节点).
同样,使用您的节点和边数很快就很难做到这一点.我担心你在最后两个问题上运气不好,除非你的图表具有可被利用的特殊属性.
如果我将图形"转换"为邻接矩阵来表示链接权重和关系类型,您认为这会有所帮助吗？是否更容易执行该算法而不是链接列表？我可以轻松地实现一个函数来在需要时进行转换.我这样说是因为我觉得在阅读了几页关于这个主题之后会更容易,但我可能错了.
不,邻接矩阵和Roy-Floyd是一个非常糟糕的主意,除非你的应用程序针对超级计算机.
这假定O(E log V)是一个可接受的运行时间,如果你在网上做某事,这可能不是,并且它需要一些更高功率的机器.
Djikstra的算法对此有好处,一次性使用.您可以保存结果以供将来使用,通过线性扫描所有顶点(或者更好的是,排序和二分搜索).
可能与上面几乎相同 - 只是使用一些功能,如果它没有正确的关系,权重将是无穷大.
与上面相同,基本上,如果您匹配这两个用户,请尽早确定.(或者,您可以"在中间见面",如果您在最短的路径上找到某人,则提前终止)
这是图表的直径,您可以在Math World上阅读.
至于邻接列表与邻接矩阵问题,它取决于图表的密集程度.此外,如果要缓存结果,那么矩阵可能就是这样.