Question

用dijkstra算法计算源点到个结点的最短路径....谢谢亲爱的朋友~ 详细答案

Answer 1

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2

Answer 2

迪杰斯特拉算法的基本思路：大致是说从一个给定的起点开始，遍历到其他结点，并且到该结点的距离要是最短。http://wenku.baidu.com/view/bef364c24028915f804dc2cf.html 参考下这个网址吧~ 看了就明白了…… 如果那个文档看不懂的话。 看这个吧~ 解释得很清楚，也有图解http://wenku.baidu.com/view/3dabd1d97f1922791688e8b4.html

Answer 3

Dijkstra算法的具体步骤：
Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。
设G=（V，E）是一个有向图，V表示顶点，E表示边。它的每一条边（i，j）属于E，都有一个非负权W（I,j），在G中指定一个结点v0，要求把从v0到G的每一个接vj（vj属于V）的最短有向路径找出来（或者指出不存在）。
基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。
基本步骤：
1、把所有结点分成两组：
第一组：包括已经确定最短路径的结点；
第二组：包括尚未确定最短路径的结点。
2、开始时，第一组只包含起点，第二组包含剩余的点；
3、用贪心的策略，按最短路径长度递增的顺序把第二组的结点加到第一组去，直到v0可达的所有结点都包含于第一组中。在这个过程中，不断更新最短路径，总保持从v0到第一组各结点的最短路径长度dist都不大于从v0到第二组任何结点的路径长度。
4、每个结点对应一个距离值，第一组结点对应的距离就是v0到此结点的最短路径长度，第二组结点对应的距离值就是v0由第一组结点到此结点的最短路径长度。
5、直到所有的顶点都扫描完毕（v0可达的所有结点都包含于第一组中），找到v0到其它各点的所有最短路径。