定义#xff1a;在给定加权图中#xff0c;选择一个顶点作为源点#xff0c;计算该源点到图中所有其他顶点的最短路径长度。

2.多源最短路问题

定义#xff1a;多源最短路问题指的是在图中存在多个起点#xff0c;需要求出从这些…1.单源最短路问题

定义在给定加权图中选择一个顶点作为源点计算该源点到图中所有其他顶点的最短路径长度。

2.多源最短路问题

定义多源最短路问题指的是在图中存在多个起点需要求出从这些起点到图中所有其他顶点的最短路径。

3.多源BFS

把所有的源点变成一个“超级源点”问题就变成了单一的单源最短路问题。

4.例题

输出[[0,0,0],[0,1,0],[1,2,1]]解法(bfs)(多个源头的最短路问题)

算法思路:

起点来一次层序遍历势必会遍历到很多重复的点。

并且如果矩阵中只有一个

换一种方式:从

0开始层序遍历并且记录遍历的层数。

当第一次碰到1的时候当前的层数就是这个

距离这一个

都放在队列中把它们当成一个整体每次把当前队列里面的所有元素向外扩展一次。

class

vv(m,vectorint(n,-1));//把所有的源点加入队列for(int

i0;im;i){for(int

j0;jn;j){if(mat[i][j]0){qe.push({i,j});vv[i][j]0;}}}//一层一层往外扩展while(qe.size()){auto

[a,b]qe.front();qe.pop();for(int

k0;k4;k){int

ybdy[k];if(x0xmy0ynvv[x][y]-1){vv[x][y]vv[a][b]1;qe.push({x,y});}}}return

vv;}

是指从一个陆地单元格走到另一个相邻上、下、左、右的陆地单元格或跨过

grid

[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

输出3

[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

输出0

vv(m,vectorbool(n,false));//将边上的1加入到队列中for(int

i0;im;i){if(grid[i][0]1)qe.push({i,0});if(grid[i][n-1]1)qe.push({i,n-1});}for(int

j0;jn;j){if(grid[0][j]1)qe.push({0,j});if(grid[m-1][j]1)qe.push({m-1,j});}while(qe.size()){auto

[a,b]qe.front();qe.pop();vv[a][b]true;for(int

k0;k4;k){int

ybdy[k];if(x0xmy0yn!vv[x][y]grid[x][y]1){qe.push({x,y});vv[x][y]true;}}}int

count0;for(int

j0;jn;j){if(grid[i][j]1vv[i][j]false)count;}}return

count;}

。

当两个格子在正东、南、西、北方向上相互紧挨着就称它们为相邻的格子。

也就是说它们有一条公共边

请你返回一个大小为

nisWater[0].size();vectorvectorint

i0;im;i){for(int

j0;jn;j){if(isWater[i][j]1){vv[i][j]0;qe.push({i,j});}}}while(qe.size()){auto

[a,b]qe.front();qe.pop();for(int

k0;k4;k){int

ybdy[k];if(x0xmy0ynvv[x][y]-1){qe.push({x,y});vv[x][y]vv[a][b]1;}}}return

vv;}

请你找出一个海洋单元格这个海洋单元格到离它最近的陆地单元格的距离是最大的并返回该距离。

如果网格上只有陆地或者海洋请返回

Manhattan

j0;jn;j){if(grid[i][j]1){vv[i][j]0;qe.push({i,j});}}}while(qe.size()){auto

[a,b]qe.front();qe.pop();for(int

k0;k4;k){int

ybdy[k];if(x0xmy0ynvv[x][y]-1){qe.push({x,y});vv[x][y]vv[a][b]1;}}}int

ret0;for(int

j0;jn;j){retmax(ret,vv[i][j]);}}if(ret0)return

-1;return