出自 MBA智库百科()
Dijkstra算法（狄克斯特拉算法）
　　Dijkstra算法是由荷兰计算机科学家（）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
　　其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。
　　举例来说，如果图中的顶点表示城市，而边上的表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
　　Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
　　这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。
　　算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。
　　在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。
function Dijkstra(G, w, s)
for each vertex v in V[G]
d[v]&:= infinity
previous[v]&:= undefined
S&:= empty set
Q&:= set of all vertices
while Q is not an empty set
// Dijstra算法主体
u&:= Extract_Min(Q)
S&:= S union {u}
for each edge (u,v) outgoing from u
if d[v] & d[u] + w(u,v)
// 拓展边(u,v)
d[v]&:= d[u] + w(u,v)
previous[v]&:= u
　　如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。
　　现在我们可以通过迭代来回溯出s到t的最短路径
1 S&:= empty sequence
3 while defined u
insert u to the beginning of S
u&:= previous[u]
　　现在序列S就是从s到t的最短路径的顶点集.
　　我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。
　　Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
　　对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。
相关问题和算法
　　在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。
　　（, ）算法是Dijkstra算法在网络路由中的一个具体实现。
　　与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。
　　与最短路径问题有关的一个问题是(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。
　　如果有已知可用来估计某一点到目标点的距离，则可改用，以减小最短路径的搜索范围。
　　电子商务是依托于互联网和信息技术的一种新型商务活动。目前,我国的电子商务发展势头迅猛,已经成为中的重要组成部分。相对于新生的来说,出现得比较早但是真正把它当作一个完整的系统来研究还是在20世纪50年代初。
　　在尤其是B2C业务开展之初,国内还没有一家物流公司具有电子商务的配送经验,各个电子商务只能求助于具有国内最大覆盖网络的速递,但是在经历一段时间之后,由于自身体制的僵化分割,管理无法协调、服务水平无法提高、费用居高不下,对很多问题都是心有余而力不足,无法满足电子商务发展的快速要求。
　　鉴于此种情景,国内的许多大型电子商务公司都在积极地寻找出路,有的自己投资组建配送队伍,但是要将自己的网点覆盖全国实在太难、投资太大有的积极寻找新近进人电子商务配送领域的配送公司,但是后来者的实力和发展速度着实无法满足需求也有求助传统的,在电子商务覆盖需求如此广大,服务环节如此复杂,业务特点往往品种多、数量少、利润低等实际问题面前,传统的往往是望而却步。
　　商品过高电子商务公司的配送不仅面向和,还要直接面对大批的者,况且电子商务不受时间、地域的限制,因此较难形成集中的、有规模的配送流量,由此造成配送任务复杂而琐碎,居高不下。降低配送,就要解决电子商务公司与物流配送企业之间在配送之间的矛盾,需要双方的共同努力。
　　一方面电子商务公司考虑,尽量将网上销售的商品控制在与协议确定的配送范围之内,并尽量使之相对集中且形成规模。
　　另一方面,物流配送企业应积极协作,选择最短路径作为配送路径降低配送成本,并加强管理,开源节流,降低物流成本和配送服务的,同时还应尽可能与电子商务公司建立长期稳定的协作关系,这样做有利于物流企业制定长远投资和服务计划,有利于加快新的的应用,加大配送渠道和设施的建设力度,最终有利于加快实现物流配送系统的、自动化、网络化和智能化从长远看,有利于持续稳定地降低物流配送的和。
　　目前关于物流配送的问题已经有很多方法,大致可分为定性和定量两大类。是指凭借个人或集体的经验来做出决策,它的执行步骤一般是先根据经验确定对各待选中心利用进行优劣性检验,根据检验结果作出决策。
　　的优点是注重历史经验、简单易行,其缺点是容易犯经验主义和主观主义的错误,并且当可选地点较多时不易做出理想的决策。根据各种约束条件和所要达到的目标,把选址问题转化为函数,再利用合适的算法进行求解,求出最符合条件的解即具体的地点作为配送路径。基于最短距离改进问题的算法的物流配。
　　一、最短路径法
　　采用图论中的最短路径算法来建立物流配送路径选择模型。它的主要思想是从代表两个顶点的距离的权矩阵开始,每次插人一个顶点比较任意两点间的已知最短路径和插人顶点作为中间顶点时可能产生的路径距离,然后取较小值以得到新的距离权矩阵。当所有的顶点均作为顶点时,得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者,即最佳的选址位置。
　　由于最短路径问题有着广泛的应用背景,国内外大量专家学者都对此问题进行了深入的研究。经典的图论与不断完善的计算机数据结构及算法的有效结合,使得新的最短路径算法不断涌现。据统计,目前提出的此类最短路径的算法大约有种。而等人对其中的17种进行了测试,结果显示有种效果比较好,它们分别是:TQQ(graph growthwith two queues)、DKA(the the Dijkstra'salgorithmimplemented with doubl ebuckets)。其中TQQ算法的基础是图增长论,用两个FIFO队列实现了一个双端队列结构来支持搜索过程,较适合于计算单源点到其他所有点的最短距离。后两种算法则是基于Dijkstra算法,采用桶结构明显提高了永久标记点的搜索速度。
　　二、算法原理及应用
　　算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的,可用来找出图中指定节点到其他节点间的最短距离。其主要思想是首先从源点求出长度最短的一条路径,然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。具体求解过程如下:
　　设wj是从源点s到节点j的最短路径长度pj是从s到的最短路径中j点的前一节点。是标识集合。是未标识集合是节点集合。dij是节点i到节点j的距离(i与j直接相连,否则)。
　　(1)S={s}；T=M-S；wj=ds；(,s与j直接相连)或,s与j不直接相连)。
　　(2)在T找节点i，使s到i的距离最小，并将i划归到S(可从与s直接相连的j中考虑)。若d_{ai}=mind_{aj}(i\inT),j与s直接相连,则将划归到中,即,,二修改中节点的值,若值改变,则。
　　(3)修改T中j节点的w_j值:wj = min(wj,wi + dij)　；若wj值改变,则pj = i。
　　(4)选定所有的wj最小值,并将其划归到S中这样就得到一个与供应商、工厂及用户间的最短距离,在费用、时间等方面的花费也相对要小得多,故可以将该选在该点处。
　　wi = minwj()；{i}；T=T{i}；若,所有节点已标识,则算法终止,否则,转人步骤(3)。
　　Dijkstra算法通用性强,既可以解决单源点间的最短路径问题,也可解决所有点对之间的最短路径问题,且编程简单。将物流中心选在与所有点对距离最近的那个点即可。
　　三、路径分析设计
　　实际生活中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征的交叉路口坐标和道路位置坐标借助于地图上的图形来识别和解释的。要对城市道路网运用Dijkstra算法求解最短路径,首先必须抽象城市道路网络为网络图论中的网络图,另外,系统要求计算道路上任意两点间的最短路径,而传统Dijkstra算法求解范围局限于任意网络节点间,不能满足要求,必须进行改进。
　　1.系统工作流程设计
　　随着城市建设的加快,城市道路网络经常发生变化,为避免经常改写代码,增强程序的和提高最短路径分析的运算效率,系统一般直接从拓扑文件提取道路网的并加载到内存中,一旦道路更新后,仅需重新抽象城市道路网络为网络图并生成拓扑文件即可。
　　(1)抽象城市道路为网络图。首先对城市道路进行编辑处理,使其与实际道路相符合,并进行拓扑检查,生成线与线相互交叉的道路图然后创建城市道路拓扑,拓扑关系构建了相邻弧段和结点之间的关系最后生成道路网络拓扑文件,文件中定义了共属性特征如弧段的起始节点、终止节点,弧段长度等,为最短路径计算准备数据。
　　(2)最短路径求解。首先读取城市道路网络图然后系统根据屏幕输入坐标,寻找道路网中的最近点作为最短路径分析的起点和终点,利用算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。
　　(3)最短路径显示与漫游。Skyline中通过程序接口读取计算结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。最短路径显示与漫游。中通过程序接口读取计算结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。
　　2.数据存储结构设计
　　ArcGIS是ESRI公司开发的一套完整的GIS应用产品,它通过对地理现象、事件及其关系进行可视化表达,构建特定的应用,提升。系统通过它进行城市道路的拓扑创建工作,并生成拓扑文件,把城市道路网抽象为关系图。系统借助ArcGIS的开发引擎ArcEngine快速访问道路拓扑图,并创建以下几个类完成网络关系图的存储及最短路径计算,如表所示。
　　四、路径效果分析
随着3S技术的飞速发展,“”成为更高层次的追求,人们越来越多地要求从三位空间处理问题。建立以配送为中心的物流服务体系。配送是发展的产物随着大批量、少批次的物流配送活动逐步被小批量、多批次所取代,个性化、多样化的越来越占有更多的,配送已成为电子商务时代物流活动的中心环节和最终目的。因此,一系列物流活动必须围绕组织配送表现出活跃的。物流企业内部的所有部门和人员都应面向配送、面向市场、面向。此外,物流企业要改变单一送货的观念,协助电子商务公司完成,提供更多的增值服务。内容,如跟踪产品订单、提供销售统计和报表等。只有这样才能紧跟电子商务的步伐,不被市场所淘汰。
　　物流配送时使用最短路径分析的算法设计。使得在配送时能够选择到配送点最短路径,降低配送成本。通过多次实验表明采用该算法准确、可靠,为在物流中的应用进一步扩展奠定了基础。
凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009,(04)
本条目对我有帮助37
&&如果您认为本条目还有待完善，需要补充新内容或修改错误内容，请。
本条目相关文档
& 1页& 4页& 3页& 3页& 3页& 2页
本条目由以下用户参与贡献
评论(共0条)提示:评论内容为网友针对条目"Dijkstra算法"展开的讨论，与本站观点立场无关。
发表评论请文明上网，理性发言并遵守有关规定。最短路径—Dijkstra算法和Floyd算法 - as_ - 博客园
随笔 - 150, 文章 - 0, 评论 - 88, 引用 - 0
Dijkstra算法
1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2.算法描述
1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则&u,v&正常有权值，若u不是v的出边邻接点，则&u,v&权值为&。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
执行动画过程如下图
3.算法代码实现：
MAXINT = 32767;
const int MAXNUM = 10;
int dist[MAXNUM];
int prev[MAXNUM];
int A[MAXUNM][MAXNUM];
void Dijkstra(int v0)
　　bool S[MAXNUM];
// 判断是否已存入该点到S集合中
int n=MAXNUM;
　　for(int i=1; i&=n; ++i)
　　dist[i] = A[v0][i];
　　S[i] = false;
// 初始都未用过该点
　　if(dist[i] == MAXINT)
　　prev[i] = -1;
　　prev[i] = v0;
　 dist[v0] = 0;
　 S[v0] = true; 　　
　　 for(int i=2; i&=n; i++)
　　int mindist = MAXINT;
　　int u = v0; 　　
// 找出当前未使用的点j的dist[j]最小值
　　 for(int j=1; j&=n; ++j)
if((!S[j]) && dist[j]&mindist)
// u保存当前邻接点中距离最小的点的号码
mindist = dist[j];
　　S[u] = true;
　　for(int j=1; j&=n; j++)
if((!S[j]) && A[u][j]&MAXINT)
　if(dist[u] + A[u][j] & dist[j])
//在通过新加入的u点路径找到离v0点更短的路径
　　dist[j] = dist[u] + A[u][j];
//更新dist
　　prev[j] =
//记录前驱顶点
4.算法实例
先给出一个无向图
用Dijkstra算法找出以A为起点的单源最短路径步骤如下
1.定义概览
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
2.算法描述
1)算法思想原理：
&&&& Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
&&&&& 从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) & Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3).Floyd算法过程矩阵的计算----十字交叉法
方法：两条线，从左上角开始计算一直到右下角 如下所示
给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点
相应计算方法如下：
最后A3即为所求结果
3.算法代码实现
typedef struct
char vertex[VertexNum];
int edges[VertexNum][VertexNum];
//邻接矩阵,可看做边表
//图中当前的顶点数和边数
void Floyd(MGraph g)
　　int A[MAXV][MAXV];
　　int path[MAXV][MAXV];
　　int i,j,k,n=g.n;
　　for(i=0;i&n;i++)
　　for(j=0;j&n;j++)
　　{ 　　
A[i][j]=g.edges[i][j];
　　 path[i][j]=-1;
　　for(k=0;k&n;k++)
　　for(i=0;i&n;i++)
　　for(j=0;j&n;j++)
　　if(A[i][j]&(A[i][k]+A[k][j]))
　　A[i][j]=A[i][k]+A[k][j];
　　path[i][j]=k;
算法时间复杂度:O(n3)注意！！用C# 写一份这个算法，实现如题要求效果_算法吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：13,144贴子：
注意！！用C# 写一份这个算法，实现如题要求效果收藏
最短路径问题&?xml:namespace prefix="o" ns="urn:schemas-microsoft-com:office:office"& &/?xml:namespace&一、实验目的1．理解贪心算法的方法；2. 掌握使用贪心算法解决一般问题的步骤；3. 掌握DIJKSTRA算法求解最短路径的方法。二、实验原理设G=(V,E)是一个每条边有非负长度的有向图，有一个顶点s称为源。单源最短路径问题，就是要确定从s到V中每一个其他顶点的距离。为简单起见，假设V={1,2,3,…,n}，并且s=1。初始时，将顶点分为两个集合X={1}和Y={2,3,…,n}。X中包含的是从源点到这些顶点的最短距离已经确认的点，而Y中包含的是从源点到这些顶点的最短距离尚未确认的点。每一步中，选定源点到它的距离已经获得的一个顶点y∈Y，并将y移入到X中。定义λ[y]为从源点出发只经过X中的顶点到y的最短距离,一旦顶点y移动到X中，与y相邻的每个顶点w∈Y的标记λ[w]就被更新，表示找到了经过y到w更短的路径。算法的思路描述如1. X←{1}; Y←V-{1}2. 对每个v∈Y，如果存在1到v的变，则令λ[v]为边的长度；否则令λ[v]=∞，并设λ[1]=03. while Y≠{}4.
令y∈Y,使λ[y]为最小5.
将y从Y移动到X6.
更新那些在Y中与y相邻的顶点的标记7. end while
为了更好地说明上述思路，将算法伪代码整理如下：算法DIJKSTRA输入：含权有向图G=(V,E)，V={1,2,…,n}输出：G中顶点1到其他顶点的距离。1. X←{1}; Y←V-{1};V={1,2,…,n}2. for y←2 to n3.
if y相邻于1 then λ[y]←length[1,y]4.
else λ[y]←∞5.
end if6. end for7. for j←1 to n-18.
令y∈Y，使得λ[y]为最小9.
X←X∪{y}10.
Y←Y-{y}11.
for 每条边(y,w)12.
if w∈Y and λ[y]+length[y,w]& λ[w] then13.
λ[w]←λ[y]+length[y,w]14.
end for15.end for代码第1行初始化X和Y两个集合；第2行～第6行初始化λ数组；第7行～第15行用于逐个找到顶点y，并依次加入到X集合，其中第8行是从Y集合中找到一个使得λ[y]最小的y顶点，第9行将y加入到X集合，第10行将y从Y集合删除，第11行～第14行将每一个和y相邻并且属于Y的顶点w的标记λ[w]进行更新，寻找那些从源点出发经过y的到达w距离更短的路径距离。代码的第1行花费时间为Θ(n)，第3行和第4行分别花费时间Θ(n)和O(n)，第8行搜索带有最小标记的顶点花费的时间为Θ(n)，这是因为算法必须检查表示Y集合的每一项（Y的长度为n），而这一个步骤执行了n-1次，因此第8行总的时间为Θ(n2)。第9行和第10行的每次迭代花费时间Θ(1)，共用了Θ(n)时间。第11行的for循环总共执行了m次（m为图中边的条数），因为每条边都检查了一次，因此耗费时间为Θ(m)。根据以上分析，Dijkstra算法总的时间复杂度是Θ(n2+m)= Θ(n2)。
三、实验内容及要求1. 编写程序使用贪心算法Dijkstra求解单源最短路径问题，并用实际的有向图进行测试。2. 要求图的数据结构采用邻接矩阵表示法。 四、实验步骤1. 编写函数DIJKSTRA求解图中顶点1到其余各顶点的最短路径，函数头为：void DIJKSTRA(int g[N][N], int lamda[N])其中g是图的邻接矩阵，N是表示图中定点数目的常量，建议采用宏定义；lamda中存储了源点到所有顶点的最短路径距离。2. 在main函数中使用给定有向图进行测试，图如下： 该图对应的邻接矩阵为： 其中∞可以用一个非常大的正整数来代替，使用宏定义#define INFINITY 9999999要求输出源点到每个顶点的最短路径长度，效果如下图所示。
矩阵0 1 12 ∞ ∞ ∞ ∞ 0 9 3 ∞ ∞ &?xml:namespace prefix="v" ns="urn:schemas-microsoft-com:vml"&&?xml:namespace prefix="o" ns="urn:schemas-microsoft-com:office:office"&&/?xml:namespace&&/?xml:namespace&∞ ∞ 0 ∞ 5 ∞ ∞ ∞ 4 0 13 15 ∞ ∞ ∞ ∞ 0 4 ∞ ∞ ∞ ∞ ∞ 0
学地理信息系统的？楼主，给个联系方式。　　　--来自OPPO Find5，发现记录你身边的美好。。。
为什么没人解答
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或}