最短路径算法是在图中求两点（或多点）之间的最短路径，我们最常见的最短路径算法有三种：Bellman-ford、Dijkstra、Floyd。

Bellman-ford算法可以用于有负边权的图，如果途图中有负环，算法也可以检验出来，时间复杂度为O(VE)。

Dijkstra算法只能用于边权为正的图中，时间复杂度为O(n^2)。

Floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的最小环和最大环。时间复杂度O（n^3）。

Dijkstra算法求单源最短路径问题

大概就是这样一个有权图，Dijkstra算法可以计算任意节点到其他节点的最短路径

算法思路

1.指定一个节点，例如我们要计算 'A' 到其他节点的最短路径
2.引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意 如上图所示，A->C由于没有直接相连 初始时为∞）
3.初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0，U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞，接下来要进行核心两步骤了
4.从U集合中找出路径最短的点，加入S集合，例如 A->D = 2
5.更新U集合路径，if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 则更新U
6.循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

算法图解

1.选定A节点并初始化，如上述步骤3所示

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B

4.思路就是这样，往后就是大同小异了

5.算法结束

参考代码

#define INF 0x7fffffff //定义一个无穷大的值
int mpt[1005][1005]; //用邻结矩阵存储图
int vis[1005];//标记每个点是否加入集合
int dist[1005];//dist[i]表示从起点到i点的最短路
void dijkstra(int s) {//传入起点坐标
    for(int i = 1; i <= n; i++)//初始化dist的值
        dist[i] = mpt[s][i];
    vis[s] = 1;//将起点加入集合
    for (int i =...

课后习题

【2016年真题】使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）
A.5,2,3,4,6    B.5,2,3,6,4
C.5,2,4,3,6    D.5,2,6,3,4

参考答案：B

【2012年真题】对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（）。 

A．d,e,f 
B．e,d,f 
C．f,d,e 
D．f,e,d 

参考答案：C
答案解析：考查 Dijkstra 算法最单源最短路径。 
从 a 到各顶点的最短路径的求解过程： 

【排除法】 对于 A，若下一个顶点为 d，路径 a,b,d 的长度 5，而 a,b,c,f 的长度仅为 4，显然错误。 
同理可以排除 B。将 f 加入集合 S 后，采用上述的方法也可以排除 D。 

【2014年真题】某网络中的路由器运行 OSPF 路由协议，题 42 表是路由器 R1 维护的主要链路状态信息(LSI)，题 42 图是根据题 42 表及 R1 的接口名构造出来的网络拓扑。 

请回答下列问题。 

1）本题中的网络可抽象为数据结构中的哪种逻辑结构？ 

2）针对题 42 表中的内容，设计合理的链式存储结构，以保存题 42 表中的链路状态信 
息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题 42 表的链式存储结构示意 
图(示意图中可仅以 ID 标识结点)。 

3）按照迪杰斯特拉(Dijikstra)算法的策略，依次给出 R1 到达题 42 图中子网 192.1.x.x 
的最短路径及费用。 

参考答案：
考察在给出具体模型时，数据结构的应用。该题很多考生乍看之下以为是网络的题目， 
其实题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考察的还是数据 
结构的内容。 
（1）图
题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 
（2）链式存储结构的如下图所示

其数据类型定义如下：

typedef struct{  
    unsigned int ID, IP;  
}LinkNode; //Link 的结构  
typedef struct{  
    unsigned int Prefix, Mask;  
}NetNode; //Net 的结构  
typedef struct Node{  
    int Flag; //Flag=1 为 Link;Flag=2 为 Net  
    union{  
        LinkNode Lnode;  
        NetNode Nnode  
    }LinkORNet;  
    unsigned int Metric;  
    struct Node *next;  
}ArcNode; //弧结点  
typedef struct HNode{  
    unsigned int RouterID;  
    ArcNode *LN_link;  
    Struct HNode *next;  
}HNODE; //表头结点  

对应题 42 表的链式存储结构示意图如下。

（3）计算结果如下表所示。

【2009年真题】带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： 
① 设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点； 
② 选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v； 
③ 重复步骤②，直到u是目标顶点时为止。 
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。 

参考答案：
该方法不一定能（或不能）求得最短路径。 
例如，对于下图所示的带权图，如果按照题中的原则，从 A 到 C 的最短路径是 A->B->C，事实上其最短路径是 A->D->C。