图之Dijkstra算法 (三)
*path)[i] = NULL;
}
}
//初始化最短路径的权值
*shortestPath = (int *)malloc(sizeof(int)*VERTEXNUM);
for(i=0;ivalue, startVertex, i, *shortestPath)) < shortest && p->vertex == j){
shortest = distance;
edgeva lue = p->value;
start = i;
end = j;
}
p = p->next;
}
}
}
}
}
vNum++;
vertexStatusArr[end] = 1;
//保存最短路径的权值
(*shortestPath)[end] = shortest;
//保存最短路径
createPath(*path, startVertex, start, end, edgeva lue);
}
}
//返回从startVertex到新的顶点的距离
int getDistance(int value, int startVertex, int start, int* shortestPath){
if(start == startVertex){
return value;
}else{
return value + shortestPath[start];
}
}
//保存最短路径
void createPath(st_edge **path, int startVertex, int start, int end, int edgeva lue){
if(start == startVertex){
st_edge* newEdge = (st_edge*)malloc(sizeof(st_edge));
newEdge->
vertex = end;
newEdge->value = edgeva lue;
newEdge->next = NULL;
st_edge** p = path + end;
while((*p) != NULL){
p = &((*p)->next);
}
*p = newEdge;
}else{
st_edge** pCopySrc = path + start;
st_edge** pCopyDes = path + end;
st_edge* newEdge = NULL;
while((*pCopySrc) != NULL){
newEdge = (st_edge*)malloc(sizeof(st_edge));
*newEdge = **pCopySrc;
newEdge->next = NULL;
*pCopyDes = newEdge;
pCopySrc = &((*pCopySrc)->next);
pCopyDes = &((*pCopyDes)->next);
}
newEdge = (st_edge*)malloc(sizeof(st_edge));
newEdge->vertex = end;
newEdge->value = edgeva lue;
newEdge->next = NULL;
*pCopyDes = newEdge;
}
}