首页 > 代码库 > Dijkstra
Dijkstra
昨天上课的时候老师讲了Dijkstra的OpenMP版本,为了给我们演示OpenMP的一些指令等,拿Dijkstra算法做了范例,自己想写写,可OpenMP的版本昨天还是没理解,没能写出来,贴一下自己未写完的代码,做个记录,等有时间了研究一下哈!
#include <iostream> #include <omp.h> //定义节点的个数 #define NUM_VERTEX 5 //定义标记数组 bool visited[NUM_VERTEX]; //定义保存最短路径的数组 unsigned int shortestPath[NUM_VERTEX]; //定义二维矩阵 unsigned int distance[NUM_VERTEX][NUM_VERTEX]; //定义线程个数 unsigned int Num_Threads; //输入数据 void input() { //输入数据 while(1) { unsigned int vertex_x , vertex_y , dist; std::cin >> vertex_x >> vertex_y >> dist; if(vertex_x ==0 && vertex_y == 0) { break; } distance[vertex_x][vertex_y] = dist; } /* //测试数据 distance[0][1] = 4; distance[1][3] = 1; distance[0][2] = 10; distance[1][2] = 3; distance[3][2] = 1; */ } //初始化路径 void initDirectPath() { memset(distance , INT_MAX , sizeof(distance)); //初始化最短路径数组 for(int i=1; i<NUM_VERTEX; ++i) { shortestPath[i] = distance[0][i]; visited[i] = false; } } //Dijkstra最短路径算法 void findShortestPathDijkstra() { for(int i=1; i<NUM_VERTEX; ++i) { //找当前最短路径的顶点 unsigned int minDistance = INT_MAX; unsigned int minVertex = 0; for(int j=1; j<NUM_VERTEX; ++j) { if(!visited[j] && shortestPath[j] < minDistance) { //记录当前最短的路径和节点编号 minVertex = j; minDistance = shortestPath[minVertex]; } } visited[minVertex] = true; //更新shortestPath for(int j=1; j<NUM_VERTEX; ++j) { if(!visited[j] && distance[minVertex][j] != distance[0][0]) {//更新距离 if(shortestPath[minVertex]+distance[minVertex][j] < shortestPath[j]) { shortestPath[j] = shortestPath[minVertex] + distance[minVertex][j]; } } } } } //输出结果 void output() { for(int i=1; i<NUM_VERTEX; ++i) { if(shortestPath[i] != distance[0][0]) { std::cout << "源点V0到顶点 " << i << " 的最短距离为 "; std::cout << shortestPath[i] << std::endl; }else{ std::cout << "源点V0到顶点 " << i << " 不可达" << std::endl; } } } //omp最短路径算法 void findShortestPathDijkstra_OpenMP() { } //检查结果 //做程序后能写检查函数的一定要写一个,检查结果是否正确 void CheckResult() { } int main() { //单线程串行版本 initDirectPath(); findShortestPathDijkstra(); output(); //omp并行版本 return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。