Dijkstra

妖狐艹你老母 2022-08-27 06:50 148阅读 0赞

昨天上课的时候老师讲了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;
    }