网站能当做创业来做吗,运营商网站登录注册,中山建设厅网站,加强网站和公众号建设迪杰斯特拉算法通常用在图的最短路径问题上
而迷宫的最短路径可以用BFS来做#xff0c;虽然BFS不能用于带权值的迷宫#xff0c;但是可以对BFS稍微改进#xff0c;只需要把判断是否走过的数组改为最短路径的数组#xff0c;在判断是否可走时判断是否比最短的小即可
Dijks…迪杰斯特拉算法通常用在图的最短路径问题上
而迷宫的最短路径可以用BFS来做虽然BFS不能用于带权值的迷宫但是可以对BFS稍微改进只需要把判断是否走过的数组改为最短路径的数组在判断是否可走时判断是否比最短的小即可
Dijkstra步骤如下
1初始化一个graph二维数组来存储图的邻接表一个dis一维数组来存储最短路径一个check来存储是否走过
2从起点开始将起点的路径设置为0也就是disp[起点] 0
3进入循环每次寻找dis中最小的节点然后遍历邻接表如果邻接表的距离该点的dis dis[循环到的点]那么就迭代循环到的点最后将最小的那个点check设置为true
while(!end()){//寻找最小的点int min max_num,min_num max_num;for(int i 1;i ::max;i){if(dis[i] min_num !check[i]){min i;min_num dis[i];}}//从邻接表中寻找这个点可到达的点并迭代可到达的点的距离for(int i 1;i ::max;i){if(graph[min][i] ! max_num){if(dis[i] dis[min] graph[min][i]){dis[i] dis[min] graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] graph[min][i]}}}//将最小的那个点标记check[min] true;}
4循环直到所有check都为true即可
也可以直接写一个函数判断
//这里写了一个函数判断是否都被标记
bool end()
{for(int i 1;i ::max;i){if(!check[i]){return false;}}return true;
} c代码如下
#include bits/stdc.h#define max_num 9999
using namespace std;int graph[max_num][max_num];//邻接表存储图
int dis[max_num];//存储最短路径
bool check[max_num];//存储是否被标记
int max;//存储最大节点//这里写了一个函数判断是否都被标记
bool end()
{for(int i 1;i ::max;i){if(!check[i]){return false;}}return true;
}void dijkstra(int e)
{while(!end()){//寻找最小的点int min max_num,min_num max_num;for(int i 1;i ::max;i){if(dis[i] min_num !check[i]){min i;min_num dis[i];}}//从邻接表中寻找这个点可到达的点并迭代可到达的点的距离for(int i 1;i ::max;i){if(graph[min][i] ! max_num){if(dis[i] dis[min] graph[min][i]){dis[i] dis[min] graph[min][i];//经过最小的那个点到达这个点的距离为dis[min] graph[min][i]}}}//将最小的那个点标记check[min] true;}
}int main()
{//初始化memset不可以用INT_MAX赋值因为INT_MAX为无符号数最大值为1111111111111111而memset会将其转换为有符号数的补码也就是-1memset(dis,max_num,sizeof(dis));memset(check, false,sizeof(check));memset(graph,max_num,sizeof(graph));int n;cin n ::max;int times n;while(times--){int x,y,z;cin x y z;graph[x][y] z;graph[y][x] z;}#if 0//输出邻接表for(int i 0;i ::max;i){for(int j 0;j ::max;j){printf(%5d ,graph[i][j]);}cout endl;}
#endif//起点启动int start;cin start;dis[start] 0;dijkstra(start);//输出每个点到起点的最短路径for(int i 1;i ::max;i){cout i : dis[i] endl;}
}
/*
10 7
1 3 2
1 2 5
2 4 9
3 4 3
3 6 2
4 6 4
4 5 8
5 6 9
5 7 3
6 2 7
1
*/
