单源最短路径问题

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
回到页面顶部