dijkstra算法邻接矩阵

A. 最短路径的Dijkstra算法

Dijkstra算法（迪杰斯特拉）是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。可以用堆优化。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
其采用的是贪心法的算法策略
大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复第2和第3步,直到OPEN表为空，或找到目标点。 #include<iostream>#include<vector>usingnamespacestd;voiddijkstra(constint&beg,//出发点constvector<vector<int>>&adjmap,//邻接矩阵，通过传引用避免拷贝vector<int>&dist,//出发点到各点的最短路径长度vector<int>&path)//路径上到达该点的前一个点//负边被认作不联通//福利：这个函数没有用任何全局量，可以直接复制！{constint&NODE=adjmap.size();//用邻接矩阵的大小传递顶点个数，减少参数传递dist.assign(NODE,-1);//初始化距离为未知path.assign(NODE,-1);//初始化路径为未知vector<bool>flag(NODE,0);//标志数组，判断是否处理过dist[beg]=0;//出发点到自身路径长度为0while(1){intv=-1;//初始化为未知for(inti=0;i!=NODE;++i)if(!flag[i]&&dist[i]>=0)//寻找未被处理过且if(v<0||dist[i]<dist[v])//距离最小的点v=i;if(v<0)return;//所有联通的点都被处理过flag[v]=1;//标记for(inti=0;i!=NODE;++i)if(adjmap[v][i]>=0)//有联通路径且if(dist[i]<0||dist[v]+adjmap[v][i]<dist[i])//不满足三角不等式{dist[i]=dist[v]+adjmap[v][i];//更新path[i]=v;//记录路径}}}intmain(){intn_num,e_num,beg;//含义见下cout<<输入点数、边数、出发点：;cin>>n_num>>e_num>>beg;vector<vector<int>>adjmap(n_num,vector<int>(n_num,-1));//默认初始化邻接矩阵for(inti=0,p,q;i!=e_num;++i){cout<<输入第<<i+1<<条边的起点、终点、长度（负值代表不联通）：;cin>>p>>q;cin>>adjmap[p][q];}vector<int>dist,path;//用于接收最短路径长度及路径各点dijkstra(beg,adjmap,dist,path);for(inti=0;i!=n_num;++i){cout<<beg<<到<<i<<的最短距离为<<dist[i]<<，反向打印路径：;for(intw=i;path[w]>=0;w=path[w])cout<<w<<<-;cout<<beg<<' ';}}

B. 生成树的标准有哪些各有什么异同

一 区别

最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。

最短路径是从一点出发，到达目的地的路径最小。

二 实现方法

1. 最小生成树

2. 最小生成树有两种算法来得到：Prims算法和Kruskal算法。

3. Kruskal算法：根据边的加权值以递增的方式，一次找出加权值最低的边来构建最小生成树，而且规定：每次添加的边不能造成生成树有回路，知道找到N-1个边为止。

4. Prims算法：以每次加入一个的临界边来建立最小生成树，直到找到N-1个边为止。其规则为：以开始时生成树的集合（集合U）为起始的定点，然后找出与生成树集合邻接的边（集合V）中，加权值最小的边来建立生成树，为了确定新加入的边不会造成回路，所以每一个新加入的边，只允许有一个顶点在生成树集合中，重复执行此步骤，直到找到N-1个边为止。

5. 2 最短路径

算法描述

(这里描述的是从节点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

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法具体步骤

（1）初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ∞(若u不是v的出边邻接点）。

（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

复杂度分析

Dijkstra 算法的时间复杂度为O(n^2)空间复杂度取决于存储方式，邻接矩阵为O(n^2)

C. 关于时间依赖的最短路径算法

Dijkstra 最短路径算法的一种高效率实现*

随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s～3 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计，目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，这些算法的具体内容可以参见文献〔1〕。其中TQQ算法的基础是图增长理论，较适合于计算单源点到其他所有点间的最短距离；后两种算法则是基于Dijkstra的算法，更适合于计算两点间的最短路径问题〔1〕。总体来说，这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的效率。
1 经典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi= ;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min〔dj, dk+lkj〕
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min〔dj, 所有未标记的点j〕
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
2 已有的Dijkstra算法的实现
从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。
网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表〔4〕 表示，其优缺点的比较见表 1。
表 1 几种图的存储结构的比较
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 称 实现方法 优 点 缺 点 时间复杂度
邻接矩阵 二维数组 1. 易判断两点间的关系 占用空间大 O(n2+m*n)
2. 容易求得顶点的度
邻接表 链表 1. 节省空间 1. 不易判断两点间的关系 O(n+m)或O(n*m)
2. 易得到顶点的出度 2. 不易得到顶点的入度
十字链表 链表 1. 空间要求较小 结构较复杂 同邻接表
2.易求得顶点的出度和入度
邻接多重表 链表 1. 节省空间 结构较复杂 同邻接表
2. 易判断两点间的关系

目前,对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA 以及 DKD 在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程〔1〕。
DKA和DKD是采用如图 1 所示的桶结构来支持这个运算，其算法的命名也来源于此。在DKA算法中，第i个桶内装有权值落在 〔b*i, (i+1)*b) 范围内的可供扫描的点，其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点有可能被多次扫描，但最多次数不会超过b次。最坏情况下，DKA的时间复杂度将会是O(m*b+n(b+C/b))，其中，C为图中边的最大权值。DKD将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点。当然随着点的插入和删除，两个桶内的点是需要动态调整的。在DKA算法中，给每个桶一定的范围以及DKD中使用双桶，在一定程度上都是以空间换时间的做法，需要改进。

图 1 一个桶结构的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra算法实现
3.1 网络拓扑关系的建立
上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、带权、出度、入度等。而GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。综合以上4种存储结构的优缺点， 笔者采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Net-Arc List），另一个则存储和顶点相关的数据（Net-Node Index）。Net-Arc List用一个数组维护并且以以弧段起点的点号来顺序排列，同一起点的弧段可以任意排序。这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示。Net-Node Index则相当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置。此外，属性数据作为GIS不可少的一部分也是必须记录的。这样，计算最佳路径所需的网络信息已经完备了。在顶点已编号的情况下，建立Net-Arc List和Net-Node Index两个表以及对Net-Arc List的排序，其时间复杂度共为O(2n+lgn)，否则为O(m+2n+lgn)。这个结构所需的空间也是必要条件下最小的，记录了m个顶点以及n条边的相关信息，与邻接多重表是相同的。图 2 是采用这个结构的示意图。
3.2 快速搜索技术的实现
无论何种算法，一个基本思想都是将点按权值的大小顺序排列，以节省操作时间。前面已经提到过，这两个算法都是以时间换空间的算法，所以在这里有必要讨论存储空间问题 (这部分空间的大小依赖于点的个数及其出度)。根据图中顶点和边的个数可以求出顶点的平均出度e=m/n（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中，e∈〔2,5〕。这样,如果当前永久标记的点为t个，那么，下一步需扫描点的个数就约为t～4t个。如果采用链表结构，按实际应用中的网络规模大小，所需的总存储空间一般不会超过100 K。所以完全没有必要采用以时间换空间的做法，相反以空间换时间的做法是完全可行的。在实现这部分时，笔者采用了一个FIFO队列，相应的操作主要是插入、排序和删除，插入和删除的时间复杂度都是O(1)，所以关键问题在于选择一个合适的排序算法。一般可供选择的排序算法有快速排序、堆排序以及归并排序等，其实现的平均时间都为O(nlgn)。经过比较实验，笔者选择了快速排序法。另外，Visual C++提供的run-time库也提供了现成的快速排序的函数qsort( )可供使用。

图 2 基于最佳路径计算的网络拓扑表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，笔者用Visual C++实现了吉奥之星（GeoStar）中的最佳路径模块。以北京的街道为数据（共6 313个结点，9 214条弧段(双向)），在主频为133、硬盘为1 G、内存为32 M的机器上，计算一条贯穿全城、长为155.06 km的线路，约需1 s～2 s。如图 3所示。

图 3 GeoStar中最佳路径实现示意图

ps:图片没有办法贴上去.
你可以参考《算法导论》第二版