对于最短路径问题，这里提供三种解决算法：BFS算法，Dijkstra算法（迪杰斯特拉），Floyd算法。

BFS求⽆权图的单源最短路径

代码实现

bool visited[MAX_VERTEX_NUM]; //访问标记数组

//广度优先遍历
void BFS(Graph G,int v){ //从定点出发，广度优先遍历图G
visit(v); //访问初始顶点v
visited[v]=TRUE; //对v做已访问标记
Enqueue(Q,v); //顶点v入队列Q
while(!isEmpty(Q)){
DeQueue(Q,v); //顶点v出队列
for(w=FirstNeighbor(G,v);
w>=0;w=NextNeighbor(G,v,w))
//检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w]=TRUE;//对w做已访问标记
EnQueue(Q,w); //顶点w入队列
}
}
}

//求顶点 u 到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for(i=0;i[HTML_REMOVED]=0;w=NextNeighbor(G,u,w))
//检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
d[w] = d[u]+1; //路径长度加1
path[w]=u; //最短路径应从u到w
visited[w]=TRUE;//设已访问标记
EnQueue(Q,w); //顶点w入队列
}
}
}

有关回顾