首页 > 代码库 > 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;
}