数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德
编辑： admin 2017-27-02
-
4
1.dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2.按dij算法求求看.
2.这句话还没找到反例...不过教floyd时说是用在非负权边上的,除了负的回路之外应该还有漏洞吧..
类似问题
类似问题1：用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中[数学科目]
是地信的题吧,先给你说v1怎么求,
先找出v1能去的最近的点,为V2,
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2,在其余的点中找距V1最近的,按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离
类似问题2：迪杰斯特拉算法问题,[数学科目]
“从V0到个重点的dist[]值和最短路径”项下第一列是从0点一步就能达到的点及路径长度,选取其中最短的一条.第二列是从0或2一步以内能够达到的点以及从0到达此点的最短长度,同样选取最短的一条.以此类推,最终形成0点达到每个点的最短距离.
类似问题3：蚁群算法和迪杰斯特拉还有弗洛伊德算法有什么区别如题不是都求最短路径吗?
蚁群算法算是属于人工智能的搜索算法.
dijkstra是单源结点最短路径.效率是o(n^2)
floyd的所有结点的最段路径.效率是0(n^3)
其实dijkstra就是估价函数为0的一种搜索.
我的了解大概是这样.
类似问题4：求佛洛依德和迪杰斯特拉算法详解[数学科目]
带权的无向图的最短路径又叫最小生成树,Prim算法和Kruskal算法；带权的有向图的最短路径算法有迪杰斯特拉算法和佛洛依德算法；
类似问题5：弗洛伊德算法Floyd和迪杰斯特拉Dijkstra算法一个三维求多源,一个二维求单源,这我明白.我现在想用下面的二维实现单源：for(i=1;i[数学科目]
4条路径 4个顶点编号为1,2,3,4
1-->4 1
4-->3 3
4-->2 1
2-->3 1
（后面为路段长度）
djkstra 是从已经确定较短路径的点出发扩展.