欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

dijkstra算法

程序员文章站 2024-01-15 19:59:52
...

看更多

算法的流程

dijkstra算法

代码

void dijkstra_main(int** test,int size,int start_pos)
{
	if(size<=0 || test == NULL || start_pos < 1)
		return ;
	dijkstra_node* sup = (dijkstra_node*)  malloc(sizeof(dijkstra_node) * size);
	int i ;
	for(i=0;i<size;i++)
	{
		sup[i].distance = 999;
		sup[i].is_get = false;
		sup[i].last_pos = -1;
	}
	sup[start_pos -1 ].is_get = true;
	sup[start_pos-1].distance = 0 ;
	sup[start_pos-1].last_pos = start_pos-1;
	stack* top = initStack(NULL,0);
	push(top,start_pos-1);
	dijkstra_core(test,sup,top,size);
}
void dijkstra_core(int** data,dijkstra_node* sup,stack* top ,int size)
{
	if(top->data == size) //已入完
		return ;
	//根据top中的头下标,找data[top头][循环] , 去更新sup的内容,
	int i = 0 ;
	for(i=0;i<size;i++) //由新进入的点,把sup表更新一遍
	{
		if(!sup[i].is_get && data[top->next->data][i]+sup[top->next->data].distance < sup[i].distance)
		{
			sup[i].distance = data[top->next->data][i]+sup[top->next->data].distance;
			sup[i].last_pos = top->next->data;
		}
	}
	int min_dist;int min_pos;
	min_dist = min_pos = 999;
	for(i=0;i<size;i++)
	{
		if(sup[i].is_get)
			continue;
		if(sup[i].distance < min_dist)
		{
			min_dist = sup[i].distance;
			min_pos = i;
		}
	}
	push(top,min_pos);
	sup[min_pos].is_get = true;
	if(top->data == 1);
	else
		printf(" %d -> %d  distance: %d  \n" ,sup[min_pos].last_pos +1 ,min_pos+1,sup[min_pos].distance);
	dijkstra_core( data, sup, top , size);
}