单源最短路径问题
template <class Type>
class Graph {
friend void main(void);
public:
void ShortestPaths(int);
private:
int n, *prev;
Type** c, *dist;
};
template <class Type>
class MinHeapNode {
friend Graph<Type>;
public:
operator int() const { return length; }
private:
int i;
Type length;
};
template <class Type>
void Graph<Type>::ShortestPaths(int v) {
MinHeap<MinHeapNode<Type>> H(1000);
MinHeapNode<Type> E;
E.i = v;
E.length = 0;
dist[v] = 0;
while (true) {
for (int j = 1; j <= n; j++) {
if ((c[E.i][j] < maxWeight) && (E.length + c[E.i][j] < dist[j])) {
dist[j] = E.length + c[E.i][j];
prev[j] = E.i;
MinHeapNode<Type> N;
N.i = j;
N.length = dist[j];
H.Insert(N);
}
try {
H.DeleteMin(E);
} catch (OutOfBounds) {
break;
}
}
}
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 16:56:10
创建日期: 2024年1月2日 16:56:10