• 所有问题

    • 数据结构之图：求所有节点之间的最短路径，用什么算法时间复杂度小？求答案与解释

    如题所述

    举报该问题
    推荐答案   2014-12-12
    两者时间复杂度一般都是O(n3)，但对于稀疏图来说重复使用Dijkstra方法比较好！
    Dijkstra算法时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂
    度变为0（v*lgn）。
    源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。
    当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
    具体详细解释你可以看看这个http://blog.chinaunix.net/uid-27164517-id-3287891.html。
    温馨提示：答案为网友推荐，仅供参考
    其他回答
    第1个回答  2014-12-12
    b
    相似回答
    最短路径算法答：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，...
    《数据结构》复习9 图【下】答：Prim从一个起点开始，逐步添加代价最小的新顶点，直至覆盖所有节点，时间复杂度为|V|轮，每轮|V|操作。而Kruskal算法则对所有边按权值排序，每次加入不形成环的新边，直至所有边相连，时间复杂度为e轮，每轮O(1)。Prim适合边稠密图，Kruskal则擅长处理边稀疏图。并查集是另一个重要的工具，用于检测图...
    计算机网络的最短路径算法有哪些?对应哪些协议?答：全局最短路径问题：求图中所有的最短路径。Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。Floyd-Warshall算法的时间复杂度为O(N^3)...
    数据结构:求最短路径,狄杰斯彻拉算法的原理是什么?最好画个图详解,谢谢...答：以上图为例进行说明，图示是寻找从V1到V5的最短路径的过程。首先，将除起点V1以外所有顶点的路径长度设为无穷大，其自身路径长度为0；1.将起点V1加入已求解的顶点集；2.检查新增的顶点的所有边，若另一顶点不在已求解顶点集内，则将其路径长度进行更新。新的路径长度为其原长与新增顶点自身路径长度...
    【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法...答：Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是 一步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。
    MST什么意思答：最短路径树是一种在图形理论中常用的数据结构，主要用于解决在一个连通图中寻找两个节点之间的最短路径问题。在计算机科学、网络、交通等领域中，最短路径树的应用非常广泛。详细解释如下：1. 基本概念：最短路径树是一种生成树算法，它能够根据图的边权重构建一棵包含图中所有节点的树，并且这棵树上...
    迪杰斯特拉算法基本信息答：迪杰斯特拉算法是一种经典的单源最短路径算法，其目标是寻找从一个起始节点到图中所有其他节点的最短路径。其主要特征是以起始点为中心，逐步向外扩展，直到扩展到目标节点。该算法在数据结构、图论和运筹学等专业课程中具有重要的地位，常作为基础知识进行讲解。算法通常有两种表述方式，这里我们采用的是...
    ...用Dijkstrath算法求计算机网络拓扑图的最短路径?答：Dijkstra算法是典型 的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一...
    floyd算法求最短路径怎么用答：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在...
    大家正在搜
    数据结构最短路径算法数据结构最短路径图解数据结构最短路径算法例题数据结构大作业最短路径算法数据结构求最短路径数据结构最短路径总结数据结构最短路径解决问题数据结构求最短路径例题数据结构最短路径知识点
    相关问题
    求“带限制条件的最短路径算法”用Dijstra算法的程序，要...
    几个关于数据结构中图的问题！
    数学建模中，给出非常多的节点，求这些节点的最短路径（类似一条...
    用Dijkstra算法求附图中从点a到其它各节点的最短路径，...
    计算机网络的最短路径算法有哪些？对应哪些协议？
    c++数据结构的图的应用，求图的最小生成树和最短路径有什么不...
    弗洛伊德算法能不能经过图上所有点?如果要求经过图上所有点的最...
    数据结构的作业 用广度优先算法求无权图的两点之间的最短路径，...