C++实现Dijkstra算法完整代码(2)

//打印到end-1的最短路径
void printPath(HeadNode *G, int end) {
  if (G[end-1].parent == -1) {
    cout << "v" << end;
  } else if (end != 0) {
    printPath(G, G[end-1].parent + 1); // 因为这里的parent表示的是下标，从0开始，所以要加1
    cout << " -> v" << end;
  }
}
int main() {
  HeadNode *G;
  int nodeNum, arcNum;
  cout << "请输入顶点个数，边长个数: ";
  cin >> nodeNum >> arcNum;
  G = new HeadNode[nodeNum];
  createGraph(G, nodeNum, arcNum);

  cout << "=============================" << endl;
  cout << "下面开始打印图信息..." << endl;
  printGraph(G, nodeNum);

  cout << "=============================" << endl;
  cout << "下面开始运行dijkstra算法..." << endl;
  Dijkstra(G, nodeNum, 1);

  cout << "=============================" << endl;
  cout << "打印从v1开始所有的最短路径" << endl;
  for (int k = 2; k <= nodeNum; k++) {
    cout << "v1到v" << k << "的最短路径为" << G[k-1].d << ": ";
    printPath(G, k);
    cout << endl;
  }
}