图的定义：图(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可以为空，此时图中只有顶点而没有边。
DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为\(O ( V )\)。
对于\(n\)个顶点\(e\)条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要\(O ( V^2 )\)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是\(O ( V + E )\)。 显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。
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算法（解决单源最短路径）：
#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
#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的优化）（适用于负权边且不能有负权回路）：
#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
图的定义：图(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可以为空，此时图中只有顶点而没有边。
DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为\(O ( V )\)。
对于\(n\)个顶点\(e\)条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要\(O ( V^2 )\)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是\(O ( V + E )\)。 显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。
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算法（解决单源最短路径）：
#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
#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的优化）（适用于负权边且不能有负权回路）：
#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
