1.单源最短路径
（1）无权图的单源最短路径
/*无权单源最短路径*/
void UnWeighted(LGraph Graph, Vertex S)
{
std::queue<Vertex> Q;
Vertex V;
PtrToAdjVNode W;
Q.push(S);
while (!Q.empty())
{
V = Q.front();
Q.pop();
for (W = Graph->G[V].FirstEdge; W; W = W->Next)
if (dist[W->AdjV] != -)
{
dist[W->AdjV] += dist[V] + ;
path[W->AdjV] = V;
Q.push(W->AdjV);
} } }
函数：返回还未被收录顶点中dist最小者
Vertex FindMinDist(MGraph Graph, int dist[], int collected[])
{
/*返回未被收录顶点中dist最小者*/
Vertex MinV, V;
int MinDist = INFINITY; for (V = ; V < Graph->Nv; ++V)
{
if (collected[V] == false && dist[V] < MinDist)
{
MinDist = dist[V];
MinV = V; //更新对应顶点
}
}
if (MinDist < INFINITY) //若找到最小值
return MinV;
else
return -;
}
（2）有权图的单源最短路径
单源最短路径Dijkstra算法
/*单源最短路径Dijkstra算法*/
/*dist数组存储起点到这个顶点的最小路径长度*/
bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S)
{
int collected[MaxVertexNum];
Vertex V, W; /*初始化，此处默认邻接矩阵中不存在的边用INFINITY表示*/
for (V = ; V < Graph->Nv; V++)
{
dist[V] = Graph->G[S][V]; //用S顶点对应的行向量分别初始化dist数组
if (dist[V] < INFINITY) //如果(S, V)这条边存在
path[V] = S; //将V顶点的父节点初始化为S
else
path[V] = -; //否则初始化为-1
collected[V] = false; //false表示这个顶点还未被收入集合
} /*现将起点S收录集合*/
dist[S] = ; //S到S的路径长度为0
collected[S] = true; while ()
{
V = FindMinDist(Graph, dist, collected); //V=未被收录顶点中dist最小者
if (V == -) //如果这样的V不存在
break;
collected[V] = true; //将V收录进集合
for (W = ; W < Graph->Nv; W++) //对V的每个邻接点
{
/*如果W是V的邻接点且未被收录*/
if (collected[W] == false && Graph->G[V][W] < INFINITY)
{
if (Graph->G[V][W] < ) //若有负边，不能正常解决，返回错误标记
return false ;
if (dist[W] > dist[V] + Graph->G[V][W])
{
dist[W] = dist[V] + Graph->G[V][W]; //更新dist[W]
path[W] = V; //更新S到W的路径
}
}
}
}
return true;
}
2.多源最短路径Floyd算法
/*多源最短路径*/
bool Floyd(MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum])
{
Vertex i, j, k; /*初始化*/
for (i = ; i < Graph->Nv; i++)
for (j = ; j < Graph->Nv; j++)
{
D[i][j] = Graph->G[i][j];
path[i][j] = -;
} for (k = ; k < Graph->Nv; k++)
for (i = ; i < Graph->Nv; i++)
for (j = ; j < Graph->Nv; j++)
{
if (D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j];
if (i == j && D[i][j] < ) //若发现负值圈，不能正常解决，返回错误标记
return false;
path[i][j] = k;
}
return true; //算法执行完毕，返回正确标记
}