dijkstra算法
程序员文章站
2024-01-15 19:59:52
...
算法的流程
代码
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);
}
上一篇: 【章节6】数据库中数据的查询操作
下一篇: go学习遇到的问题记录