图论及其应用(图论是什么专业的课程)
导语：图论
一、图的基本概念图论中的图(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,[,&39;,algorithm])功能:返回图G中start节点到end节点的最短路径
输入参数: (1) G：输入图(graph对象| digraph对象) (2) start：起始的节点 (3) end：目标的节点 (4) [&39;,algorithm]是可选的参数，表示计算最短路径的算法。一般我们不用手动设置，默认使用的是&34;，具体可设置的参数如下。
输出参数: (1) P：最短路径经过的节点 (2) d：最短距离
选项
说明
&39; (默认值)
&39;选项会自动选择算法: ●&39;用于没有边权重的graph和digraph输入。 ●&39;用于具有边权重的所有graph输入，并要求权重为非负数。 此选项还用于具有非负边权重的digraph输入。 ●&39;用于其边权重包含某些负值的digraph输入。图不能包含负循环。
&39;
广度优先计算，将所有边权重都视为1。
&39;
Dijkstra算法，要求所有边权重均为非负数。
&39; (仅适用于digraph)
适用于有向图的Bellman-Ford算法，要求图没有负循环。 尽管对于相同的问题，&39; 的速度慢于&39;，但 &39;更为通用，因为它允许某些边权重为负数。
3.2 返回任意两点的距离 D = distances(G,[,&39;,algorithm]) [Nodelist,dist] = nearest(G,s,d,[,&39;,algorithm])返回图形G中与节点s的距离在d之内的所有节点。
Nodelist是符合条件的节点dist是这些节点与s的距离3.4 可运行代码 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,&39;,G.Edges.Weight,&39;,2) set(gca,&39;,[],&39;,[]) [P,d] = shortestpath(G,9,4) % 在图中高亮出最短路径 myplot = plot(G,&39;,G.Edges.Weight,&39;,2) highlight(myplot,P,&39;,&39;) % 返回任意两点之间的距离 D = distances(G) % 找给定范围内所有的点 [Nodelist, dist] = nearest(G,2,10)Floyd-WarshalI算法(英语: Floyd-Warshall algorithm或简写为Floydalgorithm)，中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图(可以有负权重，但不可存在负权回路)的最短路径问题。
Floyd算法与迪杰斯特拉算法或贝尔曼福特算法相比，能够一次性的求出任意两点之间的最短路径，后两种算法运行一次只能计算出给定的起点和终点之间的最短路径。
当然，Floyd算法计算的时间也要高于后两种算法，其算法核心的步骤由三层循环构成。
4.1主要思想（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 if 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功能：该函数用于求解一个权重邻接矩阵任意两个节点之间的最短路径 输入： 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点结束。
本文内容由小竹整理编辑！