单源最短路问题（SSSP问题）

约定：从start到点i的距离为d。如果d==INF，说明start和i不连通。

(1) Dijkstra算法!  [邻接矩阵]

Dijkstra算法是贪心算法。它只适用于所有边的权都大于0的图。

基本思想是：设置一个顶点的集合 S，并不断地扩充这个集合，当且仅当从源点到某个点的路径已求出时它才属于集合 S。

开始时 S 中仅有源点，调整非 S 中点的最短路径长度，找当前最短路径点，将其加入到集合 S，直到所有的点都在 S 中。

时间复杂度：O(n2)

bool visited[N];     // 是否被标号 int d[N];       // 从起点到某点的最短路径长度 int prev[N];      // 通过追踪prev可以得到具体的最短路径（注意这里是逆序的） void Dijkstra(int start) { // 初始化：d[start]=0，且所有点都未被标号 memset(visited, 0, sizeof(visited));  for (int i=0; i<n; i++) d=INF;  d[start]=0; // 计算n次 for (int i=0; i<n; i++) {   int x, min=INF;   // 在所有未标号的结点中，选择一个d值最小的点x。   for (int a=0; a<n; a++) if (!visited[a] && d[a]<min) min=d[x=a];   // 标记这个点x。   visited[x]=true;   // 对于从x出发的所有边（x，y），更新一下d[y]。   for (int y=0; y<n; y++) if (d[y] > d[x]+G[x][y])   {    d[y] = d[x]+G[x][y];    prev[y] = x;      // y这个最短路径是从x走到y。   } } }

(2) 使用优先队列的Dijkstra算法*  [邻接表]

朴素的Dijkstra算法在选 d 值最小的点时要浪费很多时间，所以可以用优先队列（最小堆）来优化。

时间复杂度：O[(n＋m)logm]，最差情况（密集图）为O(n2logm)

// 需要的头文件：<queue>、<vector>、<utility> typedef pair<int, int> pii;   // 将终点和最短路径长度“捆绑”的类型 // 定义一个优先队列，d值最小的先出列 priority_queue < pii, vector<pii>, greater<pii> > q; int d[N], prev[N]; void Dijkstra(int start) {  for (int i=0; i<n; i++) d=INF;  d[start]=0; q.push (make_pair(d[start], start));   while (!q.empty()) {   // 在所有未标号的结点中，选择一个d值最小的点x。

pii u=q.top(); q.pop();   int x=u.second;   if (u.first!=d[x]) continue;  // 已经计算完    for (edge *e=adj[x]; e!=NULL; e=e->next)   {    int &v=e->v, &w=e->w;    if (d[v] > d[x]+ w)    {     d[v] = d[x]+ w;   // 松弛     prev[v]=x;     q.push(make_pair(d[v], v));    }   } } }

(3) Bellman-Ford算法  [边目录]

Bellman-Ford算法是迭代法，它不停地调整图中的顶点值（源点到该点的最短路径值），直到没有点的值调整了为止。

该算法除了能计算最短路，还可以检查负环（一个每条边的权都小于0的环）。如果图中有负环，那么这个图不存在最短路。

bool Ford(int start)      // 有负环则返回false { // 初始化 for (int i=0; i<n; i++) d=INF;  d[start]=0; for (int k=0;k<n-1;k++)    // 迭代n次   for (int i=0; i<m; i++)   // 检查每条边   {    int &x=u, &y=v;    if (d[x]<INF) d[y]=min(d[y],d[x]+w);   } // 下面的代码用于检查负环——如果全部松弛之后还能松弛，说明一定有负环 for (int i=0; i<m; i++)    // 再次检查每条边 {   int &x=u, &y=v;   if (d[y]>d[x]+w) return false; } return true; }

(4) SPFA!  [邻接表]

SPFA是使用队列实现的Bellman-Ford算法。操作步骤如下：

① 初始队列和标记数组。

② 源点入队。

③ 对队首点出发的所有边进行松弛操作（即更新最小值）。

④ 将不在队列中的尾结点入队。

⑤ 队首点更新完其所有的边后出队。

queue<int> q; bool inqueue[N];      // 是否在队列中 int cnt[N];       // 检查负环时使用：结点进队次数。如果超过n说明有负环。 bool SPFA(int start)     // 有负环则返回false { // 初始队列和标记数组 for (int i=0; i<n; i++) d=INF;  d[start]=0;  memset(cnt,0,sizeof(cnt)); q.push(start);        // 源点入队  cnt[start]++;  while (!q.empty()) {   int x=q.front(); q.pop();   inqueue[x]=false;   // 对队首点出发的所有边进行松弛操作（即更新最小值）   for (edge *e=adj[x];e!=NULL;e=e->next)   {    int &v=e->v, &w=e->w    if (d[v]>d[x]+w)    {     d[v] = d[x]+w;     // 将不在队列中的尾结点入队     if (!inqueue[v])     {      inqueue[v]=true;      q.push(v);      if (++cnt[v]>n) return false;   // 有负环     }    }   } } return true; }