一、算法步骤
建立一个队列,初始时队列里只有起始点,再建立一个数组记录起始点到所有点的最短路径(该数组的初始值要赋为极大值,该点到它本身的路径赋为0,下面的模板中该数组为dist[])。然后执行松弛操作,用队列里有的点作为起始点去刷新到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
二、算法模板
struct Edge
{
int s, e, dist; //边的起点、终点、长度 Edge() {}
Edge(int s, int e, int d) :s(s), e(e), dist(d) {}
}; const int INF = 0x3f3f3f;
const int N = + ;
vector<Edge> v[N]; //使用邻接表存储图,v[i]存储与结点i邻接的结点
int dist[N]; //存储从起点到其余各点的最短路径
int visit[N]; //存储结点是否被访问过
int n; //n为图中结点个数 void spfa(int s) //求结点s到其余各点的最短路
{
queue<int> q;
memset(dist, INF, sizeof(dist));
memset(visit, , sizeof(visit));
q.push(s);
visit[s] = ;
dist[s] = ; while (!q.empty())
{
int s = q.front();
q.pop();
visit[s] = ;
for (int i = ; i < v[s].size(); i++)
{
int e = v[s][i].e;
if (dist[e] > dist[s] + v[s][i].dist)
{
dist[e] = dist[s] + v[s][i].dist;
if (visit[e] == )
{
visit[e] = ;
q.push(e);
}
}
}
}
printf("%d\n", dist[n]);
}
三、模板题
1、hdoj2544