学习目标：

基本掌握几种重要的图论算法知识，例如Dijkstra、Floyed算法
图论算法知识是为了在实现送货机器人的路径规划时使用

---

学习内容：

1、 Dijkstra单源非负边权最短路算法

Dijkstra 算法，是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法，戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

该算法通常用来解决从源结点到其他结点的最短路径，产生一个最短路径树，算法复杂度为O(n^2)

该算法思维：从源结点开始，不断扩充已经找到最短路径的顶点集合S，对于不是在该集合的顶点，找到一个到该集合的距离最短的顶点加入到该集合中并更新它的最短路径长度，依次类推直到所有顶点都进入该集合。（该算法对于连通图而言，当然，它也可以检测一个图的连通性）

代码实现：

void dijk(int s)
{//初始化memset(path,-1,sizeof(path));/*INF使用0x3f3f3f3f的好处：* 1：满足无穷大加一个有穷的数依然是无穷大（在DijKstra算法松弛操作中避免了溢出而出现负数）* 2：满足无穷大加无穷大依然是无穷大（两个0x3f3f3f3f相加并未溢出）* 3：初始化时，由于每一个字节为0x3f，所以只需要memset（buf，0x3f,sizeof(buf)）即可*/memset(dis,0x3f,sizeof(dis)); //初始化为无穷大memset(vis,0,sizeof(vis));dis[s] = 0; //自身到自身的距离为0while(1){int k = 0;for(int j = 1; j <= n; j++){if(!vis[j]&&dis[j]<dis[k])//找未收录顶点中dis值最小的k=j; //这里第一次找到的是起点}if(!k) return; //没有未收录的点，则返回vis[k] = 1;//松弛操作for(int j = 1; j <= n; j++){//第一次循环只有起点的邻接点距离被更新，每次都更新新找到的点的邻接点if(dis[j]>dis[k]+map[k][j]){dis[j]=dis[k]+map[k][j];path[j]=k;//路径被改变，重新记录前驱，最短路是由最短路+某一条固定路组成，所以前驱是有效的}}}
}

2、Floyed多源最短路算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

该算法主要运用在对于求一个连通图中任意两个顶点之间的最短路径，算法复杂度为O(n^3)

算法思维：首先先通过将图的邻接表表示中把已知的两个顶点距离以及邻接表中某个顶点到自己的距离进行更新，然后对于任意两个点之间的距离，通过以某一个顶点作为中轴点，通过该表达式dist[i][j] = min(dist[i][k], dist[k][j])进行更新，然后邻接表中的两点间距离即为两点间的最短距离，对于求多顶点之间的最短路路径十分高效。

代码实现：

void Floyd(MatGraph g)	//求每对顶点之间的最短路径
{  int A[MAXVEX][MAXVEX];	//建立A数组int path[MAXVEX][MAXVEX];	//建立path数组int i, j, k;for (i=0;i<g.n;i++)   		for (j=0;j<g.n;j++) {  A[i][j]=g.edges[i][j];if (i!=j && g.edges[i][j]<INF)path[i][j]=i; 	//i和j顶点之间有一条边时else			//i和j顶点之间没有一条边时path[i][j]=-1;}//以上是初始化过程内容for (k=0;k<g.n;k++)		//求Ak[i][j]{   for (i=0;i<g.n;i++)for (j=0;j<g.n;j++)if (A[i][j]>A[i][k]+A[k][j])	//找到更短路径{　  A[i][j]=A[i][k]+A[k][j];	//修改路径长度path[i][j]=path[k][j]; 	//修改最短路径为经过顶点k}}DispathFloyd(g, A, path);
}	

---

学习时间：

周一至周五每日晚上7点至10点。

---

学习产出：

1、学习笔记CSDN一篇