数论和图论哪个难？图论
数论和图论哪个难？图论有向图的权重邻接矩阵（3）表示第i个节点到第j个节点的权重，其中Inf表示两个点之间没有连接，此路不通说明：（1）无向图的权重邻接矩阵为一个对称矩阵（2）主对角线元素为0，因为不存在自己到自己的权重
一、图的基本概念图论中的图(Graph) 是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 一个图 可以用数学语言描述为G(V(G) E(G))。V(vertex)指 的是图的顶点集，E(edge)指 的是图的边集。 根据边是否有方向，可将图分为有向图和无向图。另外，有些图的边上还可能有权值，这样的图称为有权图。
无向图的权重邻接矩阵
无向图
其对应的邻接矩阵为
说明：
（1）无向图的权重邻接矩阵为一个对称矩阵
（2）主对角线元素为0，因为不存在自己到自己的权重
（3）表示第i个节点到第j个节点的权重，其中Inf表示两个点之间没有连接，此路不通
有向图的权重邻接矩阵
有向图
其对应的邻接矩阵为
说明：
（1）无向图的权重邻接矩阵不再是一个对称矩阵，因为有向图3->4可以走，不代表4->3可以走
（2）主对角线元素为0，因为不存在自己到自己的权重，当然也可以存在自环权重
（3）表示第i个节点到第j个节点的权重，其中Inf表示两个点之间没有连接，此路不通
二、迪杰迪特拉（Dijkstra）算法
图中一共有5个地点，地点之间用直线连接表示可以直接到达，并且边上的数字表示两地之间最短的距离
问题：起点为0，终点为4，怎么走路程最短。
2.1思想：将所有的点划分为已经访问过的点，和为访问过的点，初始状态均为为访问的点，然后从某一个点开始，比较邻接的和已经存在的点的距离，若小就直接更新，然后挑出一个最小的访问它。
2.2具体实现过程给出如下表格，初始状态所有节点均为未访问状态，置为False，所有结点的距离均为Infinite无限远，且所有节点均不存在父节点，置为-1。
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
F |
F |
F |
F |
F |
|
Distance |
Inf |
Inf |
Inf |
Inf |
Inf |
|
Parent |
-1 |
-1 |
-1 |
-1 |
-1 |
从0出发，此时0即可被置为已访问状态True，距离为0，Parent为-1，即不存在父节点。
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
F |
F |
F |
F |
|
Distance |
0 |
Inf |
Inf |
Inf |
Inf |
|
Parent |
-1 |
-1 |
-1 |
-1 |
-1 |
此时比较与0节点相邻接的点，1节点和3节点，并且距离为4和7，均小于Inf，所以更新距离，并且更新父节点为0，
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
F |
F |
F |
F |
|
Distance |
0 |
4 |
Inf |
7 |
Inf |
|
Parent |
-1 |
0 |
-1 |
0 |
-1 |
然后从距离中挑选出一个距离最小的，路径为0->1，距离为4，然后访问这个节点
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
F |
F |
F |
|
Distance |
0 |
4 |
Inf |
7 |
Inf |
|
Parent |
-1 |
0 |
-1 |
0 |
-1 |
然后从1结点出发，可以访问2节点和3节点，距离分别为5和5，然后1->2距离为（4 5 = 9） < Inf，更新距离和父节点为1，这里实际上是从0->1->2的距离，往后面看，看完就理解了。然后1->3的距离为（4 5 = 9）> 7不更新
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
F |
F |
F |
|
Distance |
0 |
4 |
9 |
7 |
Inf |
|
Parent |
-1 |
0 |
1 |
0 |
-1 |
从未访问节点中跳出一个距离最小的节点为3节点，然后访问该节点。
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
F |
T |
F |
|
Distance |
0 |
4 |
9 |
7 |
Inf |
|
Parent |
-1 |
0 |
1 |
0 |
-1 |
再从3节点开始比较邻接点2和4的距离，3->2的距离(7 7 = 14)>9，不更新，3->4的距离（7 8 = 15）< Inf，更新距离和父节点为3
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
F |
T |
F |
|
Distance |
0 |
4 |
9 |
7 |
15 |
|
Parent |
-1 |
0 |
1 |
0 |
3 |
然后从未访问节点中，选择一个距离最小的节点进行访问，比较发现为2节点，置为已访问状态。
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
T |
T |
F |
|
Distance |
0 |
4 |
9 |
7 |
15 |
|
Parent |
-1 |
0 |
1 |
0 |
3 |
此时，从2节点出发寻找它的邻接点，找到4节点，并且2->4距离为（9 5 = 14）<15，更新距离为14，父节点为2
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
T |
T |
F |
|
Distance |
0 |
4 |
9 |
7 |
14 |
|
Parent |
-1 |
0 |
1 |
0 |
2 |
从未访问节点中寻找距离最短的那个，事实上，此时仅有一个未访问节点，直接访问即可，然后将其置为已访问状态，父节点置为2
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
T |
T |
T |
|
Distance |
0 |
4 |
9 |
7 |
14 |
|
Parent |
-1 |
0 |
1 |
0 |
2 |
至此，所有节点均访问完毕。
2.4总结：最终得到的这个表格中包含了很多信息：
|
节点 |
0 |
1 |
2 |
3 |
4 |
|
Visited |
T |
T |
T |
T |
T |
|
Distance |
0 |
4 |
9 |
7 |
14 |
|
Parent |
-1 |
0 |
1 |
0 |
2 |
（1）Distance这一行，为从0结点出发到各个节点的最短距离
（2）Parent这一行用于路径回溯，我们可以基于此找到任何一个节点的最短路径的完整路径。
比如4节点的parent节点为2，然后2节点的父节点为1，1节点的父节点为0，0没有父节点，所以从0到4的最短路径的路径向量应该是[0 1 2 4]
（3）对于距离的更新，很多人有点搞不懂，其实是这样子的，我们都有一个出发点a点，假设到了某个节点i，从a到i的距离为x，然后从i到某个点j的距离为y，如果(x y) < 列表中已经存在的值，就更新，并且此时父节点就要发生变化，变为i节点；否则不变。
2.5算法适用性（1）该算法适用于有向图和无向图，但在生活中对于求最短路径问题的话无向图居多，不可能说能从a地到b地，却不能从b地到a地。
（2）算法不能用于带负权重的图。
对于上图，迪杰斯特拉算法求出来从0到2的最短距离为2，路径为0->2，但实际上，最短距离应该为1，且路径为0->1->2
2.6如何解决不能求解含负权重的这个问题？使用贝尔曼-福特算法或者弗洛伊德算法。
对于这两个算法，大家可以自行了解。但是几乎所有的算法都不能解决带负权回路的图。
什么是负权回路？在一个图里每条边都有一个权值(有正有负)
如果存在一个环(从某个点出发又回到自己的路径)，而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路。
存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。
注意：含有负权重的无向图都是负权回路。
注意：贝尔曼-福特算法实际上处理的是具有负权重的有向图。(且该有向图也不能含有负权回路)
庆幸的是，含有负权重的图特别少见，且一旦出现负权重，也往往是在有向图中。因此大家不用担心算法求解不出来的问题。
三、matlab求解3.1计算最短路径 [P d] = shortestpath(G start end [ 'Method' algorithm])
功能:返回图G中start节点到end节点的最短路径
输入参数: (1) G：输入图(graph对象| digraph对象) (2) start：起始的节点 (3) end：目标的节点 (4) ['Method' algorithm]是可选的参数，表示计算最短路径的算法。一般我们不用手动设置，默认使用的是"auto"，具体可设置的参数如下。
输出参数: (1) P：最短路径经过的节点 (2) d：最短距离
|
选项 |
说明 |
|
'auto' (默认值) |
'auto'选项会自动选择算法: ●'unweighted'用于没有边权重的graph和digraph输入。 ●'positive'用于具有边权重的所有graph输入，并要求权重为非负数。 此选项还用于具有非负边权重的digraph输入。 ●'mixed'用于其边权重包含某些负值的digraph输入。图不能包含负循环。 |
|
'unweighted' |
广度优先计算，将所有边权重都视为1。 |
|
'positive' |
Dijkstra算法，要求所有边权重均为非负数。 |
|
'mixed' (仅适用于digraph) |
适用于有向图的Bellman-Ford算法，要求图没有负循环。 尽管对于相同的问题，'mixed' 的速度慢于'positive'，但 'mixed'更为通用，因为它允许某些边权重为负数。 |
D = distances(G [ 'Method' algorithm])3.3 找给定范围内所有的点
[Nodelist dist] = nearest(G s d [ 'Method' algorithm])
返回图形G中与节点s的距离在d之内的所有节点。
- Nodelist是符合条件的节点
- dist是这些节点与s的距离
clear;clc
s = [9 9 1 1 2 2 2 7 7 6 6 5 5 4 ];
t = [1 7 7 2 8 3 5 8 6 8 5 3 4 3 ];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s t w)
plot(G 'EdgeLabel' G.Edges.Weight 'linewidth' 2)
set(gca 'XTick' [] 'YTick' [])
[P d] = shortestpath(G 9 4)
% 在图中高亮出最短路径
myplot = plot(G 'EdgeLabel' G.Edges.Weight 'linewidth' 2)
highlight(myplot P 'EdgeColor' 'r')
% 返回任意两点之间的距离
D = distances(G)
% 找给定范围内所有的点
[Nodelist dist] = nearest(G 2 10)四、Floyd算法（弗洛伊德算法）
Floyd-WarshalI算法(英语: Floyd-Warshall algorithm或简写为Floydalgorithm)，中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图(可以有负权重，但不可存在负权回路)的最短路径问题。
Floyd算法与迪杰斯特拉算法或贝尔曼福特算法相比，能够一次性的求出任意两点之间的最短路径，后两种算法运行一次只能计算出给定的起点和终点之间的最短路径。
当然，Floyd算法计算的时间也要高于后两种算法，其算法核心的步骤由三层循环构成。
（1）假设节点i和节点j之间已经是最短路径，那么dist(i j) \leq dist(i k) dist(k j)
（2）假设i和j之间通过某个节点的距离更短，那么代表节点k很可能就是节点i和节点j最短路径上的一个点dist(i j) = dist(i k) dist(k j)
4.2算法伪代码: 1 let dist be a |V| × |V| array of minimum distances iniƟalized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u v)
5 dist[u][v] ← w(u v) // the weight of the edge (u v)
6 for each path (u v)
7 if u == v
8 path(u v) = -1
9 else
10 path(u v) = v
11 end
12 end
13 for k from 1 to |V|
14 for i from 1 to |V|
15 for j from 1 to |V|
16 if dist[i][j] > dist[i][k] dist[k][j]
17 dist[i][j] ← dist[i][k] dist[k][j]
18 path[i][j] ← path[i][k]
19 end if4.3伪代码详解
1 let dist be a |V| × |V| array of minimum distances iniƟalized to ∞ (infinity)
对于一个距离矩阵，初始化时所有距离均设置为Infinite，i==j时设置为0，因为不存在自环
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u v)
5 dist[u][v] ← w(u v) // the weight of the edge (u v)
从2到5就是得到一个邻接权重矩阵
6 for each path (u v)
7 if u == v
8 path(u v) = -1
9 else
10 path(u v) = v
11 end
12 end
6-12 为初始化path矩阵
下面的三个嵌套循环为伪代码核心部分
13 for k from 1 to |V|
中间节点
14 for i from 1 to |V|
起始节点
15 for j from 1 to |V|
终结点
16 if dist[i][j] > dist[i][k] dist[k][j]
此处对应上面的思想(1)
17 dist[i][j] ← dist[i][k] dist[k][j]
18 path[i][j] ← path[i][k]
更新dist矩阵和path矩阵
19 end if五、matlab算法实现
功能：该函数用于求解一个权重邻接矩阵任意两个节点之间的最短路径 输入： D是权重邻接矩阵 输出： dist是最短距离矩阵，其元素dist_ij表示表示i j两个节点的最短距离 path是路径矩阵，其元素path_ij表示起点为i，终点为j的两个节点之间的最短路径要经过的节点
function[dist path] = Floyd_algorithm(D)
n = 5
m = 5
% 初始化path矩阵
path = zeros(n m);
for i = 1:n
for j = 1:m
if (i == j)
path(i j) = -1;
else
path(i j) = j;
end
end
end
dist = D;
for k = 1:n
for i = 1:n
for j = 1:n
if dist(i j) > dist(i k) dist(k j)
dist(i j) = dist(i k) dist(k j);
path(i j) = path(i k);
end
end
end
end
end
、
得到的path矩阵应该怎么看？
情况一：如果path(i j)等 于j，则有两种可能：
(1) 如果dits(i j) 为Inf 则说明从i到j没有路径可以到达;
(2)如果dist(i j) 不为Inf 则说明从到可直接到达，且为最短路径。
情况二:如果path(i j)不等于j， 等于k:
这意味这从到j的最短路径.上要先从i经过k点，接着我们需要判断path(k j)是否等于j，如果等于j则下一步直接从k点走到j点；否则就重复这个步骤循环下去，直到走到j点结束。
