Question

用C++实现，求有向图中任意两个结点间的所有路径。其中图的存储结构为邻接矩阵。程序要带注释。

其中图中的顶点为1-35.邻接矩阵是这样的：





Answer 1

wait a minute

 要所有路径？还是最短路径？

追问

所有路径，好的，非常感谢。

追答

求所有路径的意义是什么？？图很大的话这路径有很多条的啊
你要求的是任意两点之间的最短距离吧？

追问

因为我这个图中有1—35，共35个结点，我想求从结点1到其它各点的所有路径。

追答

这里的所有路径，都是最短路径吧？邻接矩阵读取的是边的权重还是单纯的是否有边？

能不能把linjiejuzhen.txt的大概内容描述一下？举个简单的例子也可以

追问

不是的，比如从结点1到结点34，根据邻接矩阵，是有很多路径的。

追答

void PrintPath(int record[], int ed) {
if (record[ed] != ed) {
PrintPath(record, record[ed]);
cout << " -> ";
}
cout << ed;
}

void PrintAllPathHelper(const MGraph& G, int st, int ed, int record[]) {
if (ed == st) {
PrintPath(record, ed);
}
for (int i = 1; i < G.numVertexes; i++) {
if (G.arc[st][i] > 0 && record[i] == -1) {
record[i] = st;
PrintAllPathHelper(G, i, ed, record);
record[i] = -1;
}
}
}

void PrintAllPath(const MGraph& G, int st, int ed) {
int record[MAXVEX];
for (int i = 1; i < G.numVertexes; i++) {
record[i] = -1;
}
record[st] = st;
PrintAllPathHelper(G, st, ed, record);
}

追问

能不能改一下程序，使每两条路径之间有一个换行符，谢谢。

追答

void PrintPath(int record[], int ed) {
    if (record[ed] != ed) {
        PrintPath(record, record[ed]);
        cout << " -> ";
    }
    cout << ed;
}
 
void PrintAllPathHelper(const MGraph& G, int st, int ed, int record[]) {
    if (ed == st) {
        PrintPath(record, ed);
        cout << endl;
    }
    for (int i = 1; i < G.numVertexes; i++) {
        if (G.arc[st][i] > 0 && record[i] == -1) {
            record[i] = st;
            PrintAllPathHelper(G, i, ed, record);
            record[i] = -1;
        }
    }
}
 
void PrintAllPath(const MGraph& G, int st, int ed) {
    int record[MAXVEX];
    for (int i = 1; i < G.numVertexes; i++) {
        record[i] = -1;
    }
    record[st] = st;
    PrintAllPathHelper(G, st, ed, record);
}