最短路径--Dijkstra(狄克斯特拉)算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最短路径--Dijkstra(狄克斯特拉)算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含714字，纯文字阅读大概需要2分钟。

内容图文

最短路径

路径的概念：

      在一个无权的图中，若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减 1 。

       由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最 短路径长度 或 最短距离 。

      对于带权的图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的 路径长度 或称 带权路径长度 。

       从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为 最短路径 ，其路径长度（权值之和）称为 最短路径长度 或者 最短距离 。

 

从某个源点到其它各顶点的最短路径: Dijkstra(狄克斯特拉)算法

每一对顶点之间的最短路径: Floyed(弗洛伊德)算法

 

Dijkstra(狄克斯特拉)算法

 

基本思想： 按路径长度递增的次序求得各条路径。

 

算法描述： 设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者， 在这条路径上，必定只含一条（权值最小）弧，由此，只要在所有从源点出发的弧中查找权值最小者。

长度次短者可能有两种情况：

         1.  它可能是从源点直接到该点的路径；

         2.  也可能是：从源点先到a，再从a到该点；

其余依次类推

 

Dijkstra 算法的时间复杂度：Dijkstra 算法中的两重循环都是关于n的，所以时间复杂度为：O(n2)。

 

原文：http://blog.csdn.net/leihengxin/article/details/42237661

内容总结

以上是互联网集市为您收集整理的最短路径--Dijkstra(狄克斯特拉)算法全部内容，希望文章能够帮你解决最短路径--Dijkstra(狄克斯特拉)算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---