请以下面的代码为模版,改为堆优化的版本 bool Dijkstra(LGraph G, int dist[], int path[], Vertex S) { Vertex V = Error; AdjNode W = G->Graph[S].FirstEdge; while (W) { dist[W->AdjV] = W->Weight; path[W->AdjV] = S; W = W->Next; } dist[S] = 0; collected[S] = true; while (1) { V = FindMinDist(G, dist, collected); if (V == Error) break; else { collected[V] = true; W = G->Graph[V].FirstEdge; while (W) { if (collected[W->AdjV] == false) { if (W->Weight < 0) return false; else { if (dist[V] + W->Weight < dist[W->AdjV]) { dist[W->AdjV] = dist[V] + W->Weight; path[W->AdjV] = V; } } } W = W->Next; } } } return true; }
时间: 2024-02-10 13:26:25 浏览: 22
下面是改为堆优化版本的代码:
bool Dijkstra(LGraph G, int dist[], int path[], Vertex S)
{
Vertex V = Error;
AdjNode W = G->Graph[S].FirstEdge;
while (W)
{
dist[W->AdjV] = W->Weight;
path[W->AdjV] = S;
W = W->Next;
}
dist[S] = 0;
collected[S] = true;
MinHeap H = CreateHeap(G->Nv);
Insert(H, S, dist);
while (!IsEmpty(H))
{
V = DeleteMin(H);
collected[V] = true;
W = G->Graph[V].FirstEdge;
while (W)
{
if (collected[W->AdjV] == false)
{
if (W->Weight < 0)
return false;
else
{
if (dist[V] + W->Weight < dist[W->AdjV])
{
dist[W->AdjV] = dist[V] + W->Weight;
path[W->AdjV] = V;
if (!IsInHeap(H, W->AdjV))
Insert(H, W->AdjV, dist);
else
UpdateHeap(H, W->AdjV, dist);
}
}
}
W = W->Next;
}
}
DestroyHeap(H);
return true;
}