1. 云图网首页
  2. 技术专区
  3. 编程笔记

最短路径Ⅰ——DFS,BFS,Floyd,Dijkstra,Bellman-Ford,SPFA（含c++及Matlab代码模板）

• 编程笔记


最短路径Ⅰ

前置知识——图

在学习最短路径前，先要了解图。

图的定义：图(Graph)是由顶点的有穷非空集合/(V( G )/)和顶点之间边的集合/(E ( G )/)组成，通常表示为: /(G = ( V , E )/)，其中，/(G/) 表示个图，/(V/)是图/(G/)中顶点的集合，/(E/)是图/(G/) 中边的集合。若V = {$ v_1 , v_2 , . . . , v_n$} 则用 /(∣V∣/) 表示图/(G/)中顶点的个数，也称图/(G/)的阶，E = { $( u , v ) ∣ u ∈ V , v ∈ V $ }，用 /(∣ E ∣/)表示图/(G/)中边的条数。
注意:线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

五种最短路径算法

本文主要涉及到五种最短路径算法——深度或广度优先搜索算法，Floyd算法，Dijkstra算法，Bellman-Ford 算法，SPFA算法。

深度或广度优先搜索算法（解决单源最短路径）

DFS算法：

深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点/(w_1/)，再访问与/(w_1/) 邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
一般情况下，其递归形式的算法十分简洁。

DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为/(O ( V )/)。
对于/(n/)个顶点/(e/)条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要/(O ( V^2 )/)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是/(O ( V + E )/)。 显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。

DFS的c++代码：

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已访问标记数据
	}
	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

DFS的matlab代码：

clear all;close all;clc
%初始化邻接压缩表
b=[1 2;1 3;1 4;2 4;
   2 5;3 6;4 6;4 7];

m=max(b(:));                %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
netplot(A,1)                %形象表示

top=1;                  %堆栈顶
stack(top)=1;           %将第一个节点入栈

flag=1;                 %标记某个节点是否访问过了
re=[];                  %最终结果
while top~=0            %判断堆栈是否为空
    pre_len=length(stack);    %搜寻下一个节点前的堆栈长度
    i=stack(top);             %取堆栈顶节点
    for j=1:m
        if A(i,j)==1 && isempty(find(flag==j,1))    %如果节点相连并且没有访问过
            top=top+1;                          %扩展堆栈
            stack(top)=j;                       %新节点入栈
            flag=[flag j];                      %对新节点进行标记
            re=[re;i j];                        %将边存入结果
            break;
        end
    end
    if length(stack)==pre_len   %如果堆栈长度没有增加，则节点开始出栈
        stack(top)=[];
        top=top-1;
    end
end

A=compresstable2matrix(re);
figure;
netplot(A,1)

BFS算法：

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列Q, n个顶点均需入队一次，在最坏的情况下，空间复杂度为/(O ( V )/)。
采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)， 在搜索任一顶点的邻接点时，每条边至少访问一次，算法总的时间复杂度为/(O ( V + E )/) 。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为/(O ( V )/)，故算法总的时间复杂度为/(O ( V^2 )/)。
注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

BFS的c++代码：

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一辅助用的队列
	for(i=0; i<G.numVertexes; i++){
		//若是未访问过就处理
		if(!visited[i]){
			vivited[i] = TRUE;	//设置当前访问过
			visit(i);	//访问顶点
			EnQueue(&Q, i);	//将此顶点入队列
			//若当前队列不为空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//顶点i出队列
				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//检验i的所有邻接点
					if(!visited[j]){
						visit(j);	//访问顶点j
						visited[j] = TRUE;	//访问标记
						EnQueue(Q, j);	//顶点j入队列
					}
				}
			}
		}
	}
}

BFS的matlab代码：

clear all;close all;clc
%初始化邻接压缩表
b=[1 2;1 3;1 4;2 4;
   2 5;3 6;4 6;4 7];

m=max(b(:));                %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
netplot(A,1)                %形象表示

head=1;             %队列头
tail=1;             %队列尾，开始队列为空，tail==head
queue(head)=1;      %向头中加入图第一个节点
head=head+1;        %队列扩展

flag=1;             %标记某个节点是否访问过了
re=[];              %最终结果
while tail~=head    %判断队列是否为空
    i=queue(tail);  %取队尾节点
    for j=1:m
        if A(i,j)==1 && isempty(find(flag==j,1))    %如果节点相连并且没有访问过
            queue(head)=j;                          %新节点入列
            head=head+1;                            %扩展队列
            flag=[flag j];                          %对新节点进行标记
            re=[re;i j];                            %将边存入结果
        end
    end
    tail=tail+1;
end

A=compresstable2matrix(re);
figure;
netplot(A,1)

PS：

function A=compresstable2matrix(b)
    [n ~]=size(b);
    m=max(b(:));
    A=zeros(m,m);

    for i=1:n
        A(b(i,1),b(i,2))=1;
        A(b(i,2),b(i,1))=1;
    end

end

Dijkstra算法（解决单源最短路径）：

Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。

image

我们以上图为例，通俗点说，这个迪杰斯特拉(Dijkstra) 算法，它并不是一下子求出了/(v_0/)到$ v_8$的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

Dijkstra算法设置一个集合S记录已求得的最短路径的顶点。
在构造的过程中还设置了个辅助数组:
/(dist[]/)：记录从源点/(v_0/)到其他各顶点当前的最短路径长度，它的初态为：若从/(v_0/)到/(v_i/);有弧，则/(dist[i]/)为弧上的权值；否则置/(dist[i]/)为$∞ $。

image

例如，对图6.17中的图应用 Dijkstra算法求从顶点1出发至其余顶点的最短路径的过程，如表6.1所示。算法执行过程的说明如下。

  • 初始化：集合S初始为/(v_1/)，/(v_1/)可达/(v_2/)v和/(v_5/)，/(v_1/)不可达/(v_3/)和/(v_4/)，因此/(dist[]/)数组各元素的初值依次设置为/(dist[2]=10，dist[3]=∞ ，dist[4]=∞，dist[5]=5/)。
  • 第一轮：选出最小值/(dist[5]/)，将顶点/(v_5/) 并入集合/(S/) ,即此时已找到/(v_1/)到/(ν_5/)的最短路径。当/(v_5/) 加入/(S/)后，从/(v_1/)到集合/(S/)中可达顶点的最短路径长度可能会产生变化。因此需要更新/(dist[]/)数组。/(v_5/)可达/(v_2/) ，因/(v_1→v_5→v_2/)的距离8比/(dist[2]=10/)小，更新/(dist[2]=8/)；/(v_5/)可达/(v_3/),/(v_1→v_5→v_3/)的距离14，更新/(dist[3]=14/)；/(v_5/)可达/(v_4/)，/(v_1→v_5→v_4/)的距离7，更新/(dist[4]=7/)。
  • 第二轮：选出最小值/(dist[4]/)，将顶点/(ν_4/)并入集合/(S/)。继续更新/(dist[]/)数组。/(ν_4/)不可达/(v_2/)，/(dist[2]/)不变；/(v_4/)可达/(v_3/)，/(v_1→v_5→v_4→v_3/)的距离13比/(dist[3]/)小，故更新/(dist[3]=13/)。
    笫三轮：选出最小值/(dist[2]/)，将顶点/(ν_2/)并入集合/(S/)。继续更新/(dist[]/)数组 /(v_2/) 可达/(ν_3/)，/(v_1→v_5→v_2→v_3/)的距离9比/(dist[3]/)小，更新/(dist[3]=9/)。
  • 第四轮：选出唯一最小值/(dist[3]/)，将顶点/(v_3/) 并入集合/(S/)，此时全部顶点都已包含在/(S/)中。

显然，Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时，时间复杂度为/(O(V^2)/)。

人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 /(O(V^2)/)。

Dijkstra的c++代码：

#include<bits/stdc++.h>
using namespace std;
#define nmax 110
#define inf 999999999
/***构建所有点最短路径数组dst[],且1为源点***/
int u;/***离源点最近的点***/
int minx;
for(int i=1;i<=n;i++) dst[i]=edge[1][i];
for(int i=1;i<=n;i++) book[i]=0;
book[1]=1;
for(int i=1;i<=n-1;i++){
        minx=inf;
    for(int j=1;j<=n;j++){
        if(book[j]==0&&dst[j]<minx){
            minx=dst[j];
            u=j;
        }
    }
    book[u]=1;
    /***更新最短路径数组***/
    for(int k=1;k<=n;k++){
        if(book[k]==0&&dst[k]>dst[u]+edge[u][k]&&edge[u][k]<inf){
            dst[k]=dst[u]+edge[u][k];
        }
    }
}

Dijkstra的matlab代码：

% dist：起点与终点之间的最短距离值
% path：最短路径索引
% Distance：最短路径下的距离值
% A：邻接矩阵
% strat：起点编号
% dest：终点编号
function [dist,path,Distance] = dijkstra(A,start,dest)
% 测试数据 A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
% 测试数据 start = 1;
% 测试数据 dest = 4;
% 计算程序运行时间
tic  %开始计时
 
% 初始化操作
p = size(A,1);        %计算顶点数目 
S(1) = dest;          %初始化集合S，已加入到路径中的顶点编号
U = 1:p;              %初始化集合U，未加入到路径中的顶点编号
U(dest) = [];         %删除终点编号
Distance = zeros(2,p);  %初始化所有顶点到终点dest的距离
Distance(1,:) = 1:p;    %重赋值第一行为各顶点编号
Distance(2,1:p) = A(dest,1:p);  %重赋值第二行为邻接矩阵中各顶点到终点的距离
new_Distance = Distance;
D = Distance;            %初始化U中所有顶点到终点dest的距离
D(:,dest) = [];          %删除U中终点编号到终点编号的距离
path = zeros(2,p);  %初始化路径
path(1,:) = 1:p;    %重赋值第一行为各顶点编号
path(2,Distance(2,:)~=inf) = dest;  %距离值不为无穷大时，将两顶点相连
 
% 寻找最短路径
while ~isempty(U)  %判断U中元素是否为空
    index = find(D(2,:)==min(D(2,:)),1);  %剩余顶点中距离最小值的索引
    k = D(1,index);   %发现剩余顶点中距离终点最近的顶点编号
    
    %更新顶点
    S = [S,k];     %将顶点k添加到S中
    U(U==k) = [];  %从U中删除顶点k  
    
    %计算距离
    new_Distance(2,:) = A(k,1:p)+Distance(2,k); %计算先通过结点k，再从k到达终点的所有点距离值
    D = min(Distance,new_Distance);  %与原来的距离值比较，取最小值  
   
    %更新路径
    path(2,D(2,:)~=Distance(2,:)) = k;  %出现新的最小值，更改连接关系，连接到结点k上 
    
    %更新距离
    Distance = D;  %更新距离表为所有点到终点的最小值
    D(:,S) = [];   %删除已加入到S中的顶点
end
dist = Distance(2,start);  %取出指定起点到终点的距离值
toc %计时结束
 
% 输出结果
fprintf('找到的最短路径为：');
while start ~= dest    %到达终点时结束
    fprintf('%d-->',start);  %打印当前点编号
    next = path(2,start);    %与当前点相连的下一顶点
    start = next;            %更新当前点
end
fprintf('%d/n',dest);
fprintf('最短路径对应的距离为：%d/n',dist);
end

Floyd算法（解决多源最短路径）

定义一个n阶方阵序列/(A^{(-1)},A^{(0)},…,A^{(n-1)}/)其中，

/[A^{(-1)}[i][j]=/operatorname{arcs}[i][j]//A^{(k)}[i][j]=/operatorname{Min}/left/{A^{(k-1)}[i][j], A^{(k-1)}[i][k]+A^{(k-1)}[k][j], k=0,1, /ldots, n-1/right/}
/]

式中，/(A^{(0)}[i][j]/)是从顶点/(v_i/)到/(v_j/)、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从/(v_i/)到/(v_j/)的最短路径上就多考虑了一个顶点；经过/(n/)次迭代后，所得到的/(A^{(n-1)}[i][j]/)就是/(v_i/)到/(v_j/)的最短路径长度，即方阵/(A^{(n-1)}/)中就保存了任意一对顶点之间的最短路径长度。
image

上图所示为带权有向图G GG及其邻接矩阵。算法执行过程的说明如下。

  • 初始化：方阵/(A^{(-1)}[i][j]=arcs[i][j]/)。
  • 第一轮：将/(v_0/)作为中间顶点，对于所有顶点{ /(i , j/) }，如果有/(A^{-1}[i][j] > A^{-1}[i][0] + A^{-1}[0][j]/)，则将/(A^{-1}[i][j]/)更新为/(A^{-1}[i][0] + A^{-1}[0][j]/)。有/(A^{-1}[2][1] > A^{-1}[2][0] + A^{-1}[0][1] = 11/)，更新/(A^{-1}[2][1] = 11/)，更新后的方阵标记为/(A^0/)。
  • 第二轮：将/(v_1/)作为中间顶点，继续监测全部顶点对{ /(i , j/) } 。有/(A^{0}[0][2] > A^{0}[0][1] + A^{0}[1][2] = 10/)，更新后的方阵标记为/(A^1/)。
  • 第三轮：将/(v_2/)作为中间顶点，继续监测全部顶点对{ /(i , j/)} 。有 /(A^{1}[1][0] > A^{1}[1][2] + A^{1}[2][0] = 9/)，更新后的方阵标记为/(A^2/)。此时/(A^2/) 中保存的就是任意顶点对的最短路径长度。

应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。

image

从这个表中，可以发下一些规律：

image

可以看出，矩阵中，每一步中红线划掉的部分都不用考虑计算，只需要计算红线外的部分，节省了计算量。

Floyd算法的时间复杂度为/(O(V^3)/)。不过由于其代码很紧凑，且并不包含 其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。
Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。
也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra算法，其时间复杂度为/(O(V^3)*V = O(V^3)/)。

Floyd的c++代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 1005;
int dist[p][p];
int path[p][p];
int mp[p][p];
int n,m;
int Floyd()
{
    int i,j,k;
    for(i = 0;i < n;++i)
    {
        for(j = 0;j < n;++j)
        {
            dist[i][i]=0;
            mp[i][i]=0;
        }
    }
    int ans = MAXN;
    for(k = 0;k < n;++k){
    for(i = 0;i < n;++i)
    {
        for(j = 0;j < n;++j)
        {
            if(dist[i][k] + dist[k][j] < dist[i][j])
            {
                dist[i][j] = dist[i][k] + dist[k][j];
                path[i][j] = k;
            }
        }
    }
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int i,j;
        memset(path,-1,sizeof(path));
        memset(dist,MAXN,sizeof(dist));
        memset(mp,MAXN,sizeof(mp));
        scanf("%d %d",&n,&m);
        for(int i = 0;i < m;++i)
        {
            int x,y,d;
            scanf("%d %d %d",&x,&y,&d);
            dist[x][y]=d;
            dist[y][x]=d;
            mp[x][y]=d;
            mp[y][x]=d;
        }
        printf("%d/n",Floyd());
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                printf("%d ",dist[i][j]);
            }
            cout<<endl;
        }
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                printf("%d ",path[i][j]);
            }
            cout<<endl;
        }
    }
    return 0;
}

Floyd的matlab代码：

Floyd函数：

function [D,path,min1,path1]=floyd(a,start,terminal)
%D(i,j)表示i到j的最短路径，path(i,j)表示i到j之间的最短路径上顶点i的后继点。
%min1返回start和terminal之间的最短距离，path1返回start和terminal之间的最短路径
%a为带权邻接矩阵，start、terminal分别是起始点和终止点

D=a;n=size(D,1);path=zeros(n,n);
%n为顶点个数，生成D、path矩阵

%遍历一遍矩阵，初始化path矩阵，先将可以直接相连的点的path进行补充
for i=1:n
    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end  
    end
end

%三重遍历，查找是否有中继点可以使得路径缩短，若有则更新D、path矩阵
for k=1:n
    for i=1:n
        for j=1:n
            if D(i,k)+D(k,j)<D(i,j)
                D(i,j)=D(i,k)+D(k,j);
                path(i,j)=path(i,k);
            end 
        end
    end
%这里演示了每一步的调整过程
k,D,path
end

%判断输出参数是否为三个
if nargin==3
    min1=D(start,terminal);
    m(1)=start;
    i=1;
    path1=[ ];   
    %根据path路径一步一步跳转找到具体路径，返回path1
    while   path(m(i),terminal)~=terminal
        k=i+1;                                
        m(k)=path(m(i),terminal);
        i=i+1;
    end
    m(i+1)=terminal;
    path1=m;
end

调用函数：

w = [0,7,9,inf,inf,14;
     7,0,10,15,inf,inf;
     9,10,0,11,inf,2;
     inf,15,11,0,6,inf;
     inf,inf,inf,6,0,9;
     14,inf,2,inf,9,0];
 start=1;terminal=5;
[D,path,min,path1]=floyd(w,start,terminal);
D,path,min,path1

Bellman-Ford 算法（解决负权边）：

Dijkstra算法虽然好，但是它不能解决带有负权边（边的权值为负数）的图。

接下来学习一种无论在思想上还是在代码实现上都可以称为完美的最短路径算法：Bellman-Ford算法。

Bellman-Ford算法非常简单，核心代码四行，可以完美的解决带有负权边的图。

for(k=1;k<=n-1;k++)  //外循环循环n-1次，n为顶点个数
    for(i=1;i<=m;i++)//内循环循环m次，m为边的个数，即枚举每一条边
        if(dis[v[i]]>dis[u[i]]+w[i])//尝试对每一条边进行松弛，与Dijkstra算法相同
            dis[v[i]]=dis[u[i]]+w[i];

在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边，最短路径中不可能包含回路。

因为最短路径是一个不包含回路的简单路径，回路分为正权回路(回路权值之和为正)和负权回路(回路权值之和为负)。如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径；如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径. 因此最短路径肯定是一个不包含回路的最短路径，即最多包含n-1条边。

Bellman-Ford算法的主要思想：

首先dis数组初始化顶点u到其余各个顶点的距离为∞，dis[u] = 0。

然后每轮对输入的所有边进行松弛，更新dis数组，至多需要进行n-1次就可以求出顶点u到其余各顶点的最短路径（因为任意两点之间的最短路径最多包含n-1条边，所以只需要n-1轮就行）。

一句话概括Bellman-Ford算法就是：对所有边进行n-1次“松弛”操作。

此外，Bellman-Ford算法可以检测一个图是否有负权回路。如果已经进行了n-1轮松弛之后，仍然存在

if(dis[v[i]]>dis[u[i]]+w[i])
    dis[v[i]]=dis[u[i]]+w[i];

的情况，也就是说在进行n-1轮之后，仍然可以继续成功松弛，那么这个图一定存在负权回路。

关键代码如下：

//Bellman-Ford算法核心语句
for(k=1;k<=n-1;k++)  //外循环循环n-1次，n为顶点个数
    for(i=1;i<=m;i++)//内循环循环m次，m为边的个数，即枚举每一条边
        if(dis[v[i]]>dis[u[i]]+w[i])//尝试对每一条边进行松弛，与Dijkstra算法相同
            dis[v[i]]=dis[u[i]]+w[i]; 
//检测负权回路
flag=0;
for(i=1;i<=m;i++)
    if(dis[v[i]]>dis[u[i]]+w[i])
        flag=1;
if(flag==1)
    printf("此图有负权回路");

显然，算法复杂度为O（NM），比Dijkstra算法还高，当然可以进行优化。

在实际操作中，Bellman-Ford算法经常会在没有达到n-1轮松弛前就已经计算出最短路，上面已经说过，n-1其实是最大轮回次数。

因此可以添加一个变量check用来标记数组dis在本轮松弛中是否发生了变化，若没有变化，则提前跳出循环。

Bellman-Ford算法的c++代码：

#include <iostream>
#define INF 1e9
 
void DFSPrint(int bak[], int k)
{
    if (bak[k] == k)
    {
        printf("%d ", k);
        return;
    }
    DFSPrint(bak, bak[k]);
    printf("%d ", k);
    return;
}
 
int main()
{
    int i, j, n, m;
    int dis[10], bak[10], u[10], v[10], w[10];
    int check;
 
    // 读入n和m, n表示顶点个数,m表示边的条数
    scanf("%d %d", &n, &m);
 
    // 读入边
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &u[i], &v[i], &w[i]);
    }
 
    // 初始化bak[]数组，前驱结点均为自己
    // 初始化dis[]数组，源点为1号顶点
    for (i = 1; i <= n; ++i)
    {
        bak[i] = i;
        dis[i] = INF;
    }
    dis[1] = 0;
 
    // Bellman-Ford算法
    for (j = 1; j <= n-1; ++j)  // 最多循环n-1轮（图退化为链表）
    {
        check = 0;  // 用来标记在本轮松弛中数组dis是否发生更新
        for (i = 1; i <= m; ++i)
        {
            if (dis[u[i]] != INF && dis[u[i]] + w[i] < dis[v[i]])  // relax
            {
                dis[v[i]] = dis[u[i]] + w[i];
                bak[v[i]] = u[i];
                check = 1;
            }
        }
 
        if (check == 0)
        {
            break;
        }
    }
 
    // 检测负权回路,若存在,则在对边进行一次遍历后必定会有relax的操作
    int flag = 0;
    for (i = 1; i <= m; ++i)
    {
        if (dis[u[i]] + w[i] < dis[v[i]])
        {
            flag = 1;
        }
    }
 
    if (flag)
    {
        printf("该图有负权回路");
    }
    else
    {
        // 输出最终结果
        printf("最终结果为:/n");
        for (i = 1; i <= n; ++i)
        {
            printf("1号顶点到%d号顶点的最短距离为:%d/n", i, dis[i]);
        }
        printf("/n打印1号顶点到5号顶点的最短路径:/n");
 
        DFSPrint(bak, 5);
    }
 
    return 0;
}

Bellman-Ford算法的matlab代码：

function [flag]=bellmanford()
% 输出：是否存在可行解
    %G—图的邻接矩阵表示，元素值为权重
    G =[3 7 2 10;1 4 4 5;1 10 8 5;9 1 8 7];
    %源点
    s = 1;
    dis = ones(1,size(G,1))*inf;
    %初始化
    dis = init(G,s,dis);
    %执行松弛操作
    for l=1:size(G,1)-1
        for j=1:size(G,1)
            for k=1:size(G,1)
                dis = relax(G,j,k,dis);
            end
        end
    end
    %判断是否存在权重为负值的环路
    for m=1:size(G,1)
        for n=1:size(G,1)
            %是否存在估计错误的情况，若存在，则代表存在权重为负值的环
            if dis(n)>dis(m) + G(m,n)
                flag = 0;
                return;
            end
        end
    end
    flag = 1;
    %输出可行解
    dis
end

%dis：最短路径估计值数组
%G：图的邻接表表示法，元素代表行数i到列数j之间边的权重
function [dis] = init(G,s,dis)
    for i=1:size(G,1)
        dis(i) = inf;
    end
    dis(s) = 0;%源点的距离为0
end

%dis：最短路径估计值数组
%G：图的邻接表表示法，元素代表行数i到列数j之间边的权重
function [dis] = relax(G,u,v,dis)
    %dis(v):表示G中从源点到点v的距离估计值，若估计值大于前驱节点的距离+u和v的距离，则更新
	if dis(v)>dis(u)+G(u,v)
        dis(v) = dis(u)+G(u,v);
 	end
end

SPFA算法（对bellman – ford的优化）（适用于负权边且不能有负权回路）：

一般情况下SPFA算法也可以解决正权边问题，且时间比Dijkstra更快（但是如果出题人卡掉了SPFA算法，就只能用Dijkstra算法了）

我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

期望的时间复杂度/(O(ke)/)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。

建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

SPFA的c++代码：

最朴素的模板：

#include <stdio.h>
#include <string.h>

const int N = 1010, M = 2e6, INF = 1e9;

int n, m;	//n是节点数，m是边数
int dist[N], q[N];	//dist[i]表示源点到i点的最短距离
int h[N], to[M], w[M], ne[M], idx;	//idx初始化为0
bool st[N];	//储存每个点是否在队列中

//添加边表示a到b有一条单向边，权值为c
void add(int a, int b, int c){
    to[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

//求源点s到其它点的最短路径
void spfa(int s){
    int hh, tt;	//队列头指针和尾指针
    memset(st, false, sizeof(st));
    for(int i = 1; i <= n; i++) dist[i] = INF;
   	dist[s] = 0;
    q[tt++] = s;
    st[s] = true;
    while(hh != tt){	//队列不为空
        int t = q[hh++];
        st[t] = false;
        if(hh == N) hh = 0;
        for(int i = h[i]; ~i; i = ne[i]){
            if(dist[t] + w[i] < dist[to[i]]){
                dist[to[i]] = dist[t] + w[i];
                if(!st[to[i]]){
                    st[to[i]] = true;
                    q[tt++] = to[i];
                    if(tt == N) tt = 0;
                	}
            	}
        	}
    	}
}

int main(void){
    int a, b, c;
    scanf("%d %d %d", &n, &m, &s);
    memset(h, -1, sizeof(h));
    for(int i = 1; i <= m; i++){
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    	}
   	spfa(s);
    for(int i = 1; i <= n; i++){
        if(dist[i] == INF) puts("NO PATH");
        else printf("%d/n", dist[i]);
    	}
   	return 0;
}

SLF优化的SPFA算法：

SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。

#include <stdio.h>
#include <string.h>
#include <deque>
using namespace std;

const int N = 1010, M = 2e6, INF = 1e9;

int dist[N];
int h[N], to[M], w[M], ne[M], idx;
bool st[N];
int n, m;

void add(int a, int b, int c){
    to[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(int s){
    memset(st, false, sizeof(st));
    for(int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    deque<int> q;
    q.push_front(s);
    st[s] = true;
    while(!q.empty()){
        int t = q.front();
        q.pop_front();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            if(dist[t] + w[i] < dist[to[i]]){
                dist[to[i]] = dist[t] + w[i];
                if(!st[to[i]]){
                    if(!q.empty() && dist[to[i]] < dist[q.front()]){
                        q.push_front(to[i]);
                    	}
                    else q.push_back(to[i]);
                    st[to[i]] = true;
                	}
            	}
        	}
    	}
}

SPFA的matlab代码：

function Bellman_Ford(d,n,s)
%d为已知图的邻接矩阵，n为顶点数（各顶点标号为1,2,...,n），s为源点标号
for i=1:n %初始化dist，pre
    dist(i)=inf; %dist(i)为s，i之间的最短路的长度
    pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
end
dist(s)=0;
for k=1:n-1
    for i=1:n 
        for j=1:n
            if d(i,j)~=inf
                if dist(j)>dist(i)+d(i,j)
                    dist(j)=dist(i)+d(i,j);
                    pre(j)=i;
                end
            end
        end
    end
end
for i=1:n
    for j=1:n
        if d(i,j)~=inf
            if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                error('Negetive WeightCircut');
            end
        end
    end
end
dist
pre
end

clc;clear
w=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
      8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
      inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0];
i=1;m=8;

Bellman_Ford(w,m,i)

原创文章，作者：745907710，如若转载，请注明出处：https://blog.ytso.com/275191.html

赞 (0)
0
上一篇 2022年7月18日
下一篇 2022年7月18日

相关推荐

发表回复

登录后才能评论