图论模型可以简单理解为画图解决的模型。比较经典的有树状图、TSP算法等等。其中上一篇文章中提到的动态规划也看作图论的一种。

图论模型可以简单的分为以下几种：

1. 最短路径问题
2. 最小生成树问题
3. 网络最大流问题
4. 排队问题

接下来一一解释，并给出常见的算法。值得注意的是，以上都可以看作是或转化单目标优化。

1.最小路径问题
1.1经典的问题是路径规划问题，即求一个点到另一个点的最短路径。（无权）
思路：
**1.遍历法，**广度优先（钻井，先把每一层都扩建到最大再打下一层），按照树图的思想以起点为中心，分层，分层的层数与A的跳数相同。查看每一个节点的下一跳，求出所有解法后找到最佳的一条。
PS：深度优先（钻井直接钻到最深处，再返回扩建）：
(1)首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；
(2)当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。

两种思路的目的：在图论问题中，遍历中如果没有准则依靠来寻找的话容易去到之前取得过的路径造成浪费，因此我们一般基于这两种思想。

1.2 路径规划加权情况（每一跳长度不一样）：
无法使用广度优先进行遍历，但是依然用遍历的方法解决。
2.DJ斯特拉算法
这个算法的本质，是不断刷新起点与其他各个顶点之间的 “距离表”。这个图的表现和我们之前有提到过的动态规划在底层逻辑一样。本算法的遍历依然是基于广度优先。

第1步，创建距离表。表中的Key是顶点名称，Value是从起点A到对应顶点的已知最短距离。但是，一开始我们并不知道A到其他顶点的最短距离是多少，Value默认是无限大：

第2步，遍历起点A，找到起点A的邻接顶点B和C。从A到B的距离是5，从A到C的距离是2。把这一信息刷新到距离表当中。每一次遍历更新一遍最短距离。

第三步，A遍历完后，遍历B,C的子层。一直到遍历完成为止。代码引自：程序员小灰

/**

* Dijkstra最短路径算法

*/

public static Map<Integer, Integer> dijkstra(Graph graph, int startIndex) {

//创建距离表，存储从起点到每一个顶点的临时距离

Map<Integer, Integer> distanceMap = new HashMap<Integer,Integer>();

//记录遍历过的顶点

Set<Integer> accessedSet = new HashSet<Integer> ();

//图的顶点数量

int size = graph.vertexes.length;

//初始化最短路径表，到达每个顶点的路径代价默认为无穷大

for(int i=1; i<size; i++){

distanceMap.put(i, Integer.MAX_VALUE);

}

//遍历起点，刷新距离表

accessedSet.add(0);

List<Edge> edgesFromStart = graph.adj[startIndex];

for(Edge edge : edgesFromStart)

{

distanceMap.put(edge.index, edge.weight);

}

//主循环，重复 遍历最短距离顶点和刷新距离表 的操作

for(int i=1; i<size; i++)

{

//寻找最短距离顶点

int minDistanceFromStart = Integer.MAX_VALUE;

int minDistanceIndex = -1;

for(int j=1; j<size; j++)

{

if(!accessedSet.contains(j) && distanceMap.get(j) < minDistanceFromStart)

{

minDistanceFromStart = distanceMap.get(j);

minDistanceIndex = j;

}

}

if(minDistanceIndex == -1){

break;

}

//遍历顶点，刷新距离表

accessedSet.add(minDistanceIndex);

for(Edge edge : graph.adj[minDistanceIndex])

{

if(accessedSet.contains(edge.index)){

continue;

}

int weight = edge.weight;

int preDistance = distanceMap.get(edge.index);

if(weight != Integer.MAX_VALUE && (minDistanceFromStart+ weight < preDistance))

{

distanceMap.put(edge.index, minDistanceFromStart + weight);

}

}

}



return distanceMap;

}



public static void main(String[] args) {

Graph graph = new Graph(7);

initGraph(graph);

Map<Integer, Integer> distanceMap = dijkstra(graph, 0);

int distance = distanceMap.get(6);

System.out.println(distance);

}



/**

* 图的顶点

*/

private static class Vertex {

String data;

Vertex(String data) {

this.data = data;

}

}



/**

* 图的边

*/

private static class Edge {

int index;

int weight;

Edge(int index, int weight) {

this.index = index;

this.weight = weight;

}

}



/**

* 图

*/

private static class Graph {

private Vertex[] vertexes;

private LinkedList<Edge> adj[];



Graph(int size){

//初始化顶点和邻接矩阵

vertexes = new Vertex[size];

adj = new LinkedList[size];

for(int i=0; i<adj.length; i++){

adj[i] = new LinkedList<Edge>();

}

}

}



private static void initGraph(Graph graph){

graph.vertexes[0] = new Vertex("A");

graph.vertexes[1] = new Vertex("B");

graph.vertexes[2] = new Vertex("C");

graph.vertexes[3] = new Vertex("D");

graph.vertexes[4] = new Vertex("E");

graph.vertexes[5] = new Vertex("F");

graph.vertexes[6] = new Vertex("G");



graph.adj[0].add(new Edge(1, 5));

graph.adj[0].add(new Edge(2, 2));

graph.adj[1].add(new Edge(0, 5));

graph.adj[1].add(new Edge(3, 1));

graph.adj[1].add(new Edge(4, 6));

graph.adj[2].add(new Edge(0, 2));

graph.adj[2].add(new Edge(3, 6));

graph.adj[2].add(new Edge(5, 8));

graph.adj[3].add(new Edge(1, 1));

graph.adj[3].add(new Edge(2, 6));

graph.adj[3].add(new Edge(4, 1));

graph.adj[3].add(new Edge(5, 2));

graph.adj[4].add(new Edge(1, 6));

graph.adj[4].add(new Edge(3, 1));

graph.adj[4].add(new Edge(6, 7));

graph.adj[5].add(new Edge(2, 8));

graph.adj[5].add(new Edge(3, 2));

graph.adj[5].add(new Edge(6, 3));

graph.adj[6].add(new Edge(4, 7));

graph.adj[6].add(new Edge(5, 3));
————————————————
原文链接：https://blog.csdn.net/bjweimengshu/article/details/89090053

那么接下来分析复杂度，每一次的dj都会造成O（n2）的算法复杂度，如果遍历每一个顶点之间的最小距离，算法复杂度可以达到O(n3)复杂度较高。

缺陷：复杂度高，且没有路径输出，只输出了最佳长度是。
进阶：弗洛伊德算法
基本思想：最短路径有两种得出方法：
1.直接最短
2.有其他邻接，加和最短。

首先生成距离矩阵，如A-G（图片来自程序员小灰）

依次将a,ab,abc,…作为中继点带入，不断更新最短路径。
这样就可以得出最终的任意两点之间最短路径长度了，也可以根据矩阵计算出路径了。

final static int INF = Integer.MAX_VALUE;



public static void floyd(int[][] matrix){

//循环更新矩阵的值

for(int k=0; k<matrix.length; k++){

for(int i=0; i<matrix.length; i++){

for(int j=0; j<matrix.length; j++){

if(matrix[i][k] == INF || matrix[k][j] == INF) {

continue;

}

matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);

}

}

}

// 打印floyd最短路径的结果

System.out.printf("最短路径矩阵: \n");

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix.length; j++)

System.out.printf("%3d ", matrix[i][j]);

System.out.printf("\n");

}

}






public static void main(String[] args) {

int[][] matrix = {

{0, 5, 2, INF, INF, INF, INF},

{5, 0, INF, 1, 6, INF, INF},

{2, INF, 0, 6, INF, 8, INF},

{INF, 1, 6, 0, 1, 2, INF},

{INF, 6, INF, 1, 0, INF, 7},

{INF, INF, 8, 2, INF, 0, 3},

{INF, INF, INF, INF, 7, 3, 0}

};

floyd(matrix);


————————————————
版权声明：本文为CSDN博主「程序员小灰」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/bjweimengshu/article/details/89702338

如此可以非常快速解决一些经典的最短路径问题。