#include using namespace std; #define MAX 9999 //定义无穷大 /* **Graph 类，用以存放有关图的所有信息 */ class Graph { public: //--------------------------- //param int 初始节点编号 //-------------------------- void ShorestPaths(int); void ShowDist(); Graph(); private: int n; //图的节点个数 int *prev; //存放顶点的前驱节点 int **c; //存放图的邻接矩阵 int *dist; //存放源点到各个顶点的距离 }; /* **节点 */ class MinHeapNode { friend Graph; public: int getI() {return i;} void setI(int ii) { i = ii; } int getLength(){return length;} void setLength(int len) { length = len; } private: int i; //顶点编号 int length; //当前路长 }; /* **最小堆 */ class MinHeap { friend Graph; public: MinHeap(); MinHeap(int); void DeleteMin(MinHeapNode &); void Insert(MinHeapNode); bool OutOfBounds(); private: int length; MinHeapNode *node; }; Graph::Graph() { int wi = 0; int yi = 0; cout<<"请输入图的节点个数："; cin>>n; cout<<"请输入图的邻接矩阵：(无穷大请以9999 代替)" << endl; c = new int*[n+1]; dist = new int[n+1]; prev = new int[n+1]; //------------------------------ //初始化邻接矩阵 //------------------------------ for (wi = 0; wi <= n; wi++) { c[wi] = new int[n+1]; if (wi == 0) { for (yi = 0; yi <= n; yi++) { c[wi][yi] = 0; } } else { for (yi = 0; yi <= n; yi++) { if (yi == 0) { c[wi][yi] = 0; } else { cin >> c[wi][yi]; } } } } //---------------------------------- //初始化数组 //---------------------------------- for (wi = 0; wi <= n; wi++) { dist[wi] = MAX; prev[wi] = 0; } } void Graph::ShowDist() { cout << "从源点到该节点的最短路径:" << endl; int i = 0; int temp = 0; for (i = 1; i <= n; i++) { cout << "dist[" << i << "] = " << dist[i] << endl; } cout << "从源点到终点的最短路径长度为:" << dist[n] << endl; cout << "其...
VIP
