#include "Dijk_11_14.h"
#include <stdio.h>
struct NodeState* newNodeState(int number)
{
struct NodeState * pNodeState;
pNodeState = (struct NodeState *)malloc(sizeof(struct NodeState )*(number + 1));
return pNodeState;
}
void initState(struct NodeState *pNodeState)
{
struct NodeState* pState;
//初始化节点state
for(pState = &pNodeState[0]; pState <= &pNodeState[NODENUM]; pState++)
{
pState->pre = -1;
pState->length = INFINITY;
pState->label = tentative;
}
return;
}
/*dijkstra算法，返回节点状态列表*/
void getNodeState(int src, struct NodeState* pNodeState, int adjacency[NODENUM][NODENUM])
{
int i, k, min;
struct NodeState* pState;
pNodeState[src].length = 0;
pNodeState[src].label = permanent;
k = src;//k is the current node under working
do
{
for(i = 1; i<= NODENUM; i++)
{
if( (i != k)&&pNodeState[i].label == tentative)
{
if(pNodeState[k].length + adjacency[k][i] < pNodeState[i].length)
{
pNodeState[i].length = pNodeState[k].length + adjacency[k][i];
pNodeState[i].pre = k;
}
}
}
k = 1;
min = INFINITY;
for(i = 1; i<= NODENUM; i++)
{
if(pNodeState[i].label == tentative && pNodeState[i].length < min)
{
k = i;
min = pNodeState[i].length;
}
}
if(pNodeState[k].label = permanent)
{
break;//已经是permanent， 说明没找到
}
else
{
pNodeState[k].label = permanent;
}
}while(k != src);
return ;
}
//获得src到dst的最短路径
struct P2pPath *getDijkstraPath(int src, int dst, struct NodeState *pNodeState)
{
int i = 0;
int k = 0;
int count = 0;
struct P2pPath *pPath;
pPath = (struct P2pPath *)malloc(sizeof(struct P2pPath ));
k = dst;
do
{
pPath->path[i++] = k;
k = pNodeState[k].pre;
count++;
}while(k >= 0);
pPath->length = count;
//打印路径
//for(i = 1; i <= pPath->length; i++)
printf("从源节点的%d到目的节点%d的详细路径：", src, dst);
for( i = pPath->length-1 ; i >=0 ;i--)
{
printf("%d ",pPath->path[i]);
}
return pPath;
}
评论0