C++ 图的广度优先遍历 ，如何再次基础上算出其最短路径

Question

#include "error.h"
#include "random.h"
#include "Vector.h"
#include "Set.h"
#include "queue.h"

#ifdef _MAP_H
#define _MAP_H

#endif

struct nodeT;

struct arcT{
int distance;
std::string name;
nodeT *start,*end;
};

struct nodeT{
//node (name etc)

std::string name;
Vector<arcT*> outgoing;
};

/*深度优先遍历*/
void Depth(nodeT *cur,Set<std::string> &visited)
{
if(visited.contains(cur->name)) return;
visited.add(cur->name);

for(int i = 0;i<cur->outgoing.size();i++)
{
Depth(cur->outgoing[i]->start,visited);
Depth(cur->outgoing[i]->end,visited);
}
}

/*最短路径问题？*/
/*迷宫问题？*/
/*how to print the route*/
/**
如何打出他们所有的联通路径
然后算出他们的最短路径
*/
void BreadFirstSearch(nodeT * start)
{
Queue<nodeT*> q;
Set<std::string> visited;
q.enqueue(start);

while(!q.isEmpty())
{
nodeT* cur=q.dequeue();
if(!visited.contains(cur->name))
{
visited.add(cur->name);
for(int i = 0;i<start->outgoing.size();i++)
q.enqueue(cur->outgoing[i]->end);
}
}
}

void PrintBreadFirstSearch(nodeT * start)
{
Queue<nodeT*> q;
Set<std::string> visited;
q.enqueue(start);

while(!q.isEmpty())
{
nodeT* cur=q.dequeue();

cout<<"遍历的节点名称"<<cur->name<<endl;

if(!visited.contains(cur->name))
{
visited.add(cur->name);
for(int i = 0;i<cur->outgoing.size();i++)
q.enqueue(cur->outgoing[i]->end);
}
}
}

/*广度优先遍历*/

int main(int argc, char **argv)
{
nodeT *A,*B,*C;

A =(nodeT*) new nodeT;
B=(nodeT*) new nodeT;
C =(nodeT*) new nodeT;

A->name = "A";
B->name = "B";
C->name = "C";
arcT *arc1,*arc2,*arc3;
arc1 =(arcT*) new arcT;
arc2 =(arcT*) new arcT;
arc3 =(arcT*) new arcT;

arc1->distance = 10;
arc1->name = "a1";
arc1->start = A;
arc1->end = B;

arc2->distance = 20;
arc2->name = "a2";
arc2->start = A;
arc2->end = C;

arc3->distance = 7;
arc3->name = "a3";
arc3->start = B;
arc3->end = C;

A->outgoing.add(arc1);
A->outgoing.add(arc2);
B->outgoing.add(arc3);

PrintBreadFirstSearch(A);

system("pause");
return 0;
}

Answer 1

（1）由于你的深度遍历记录结点或弧，只记录了结点名，因此，不能根据visited集合打印出最短距离
（2）由于路径必须设定起、始结点，因此，也不能简单根据visited或一个结点打印出两点间任意路径。
实事上：
(1)你可以用Dijistra算法求任意两点间短径
(2)用深度遍历结合回溯算法求两点间所有路径
这两个算法你可以在网上搜索到。