1.例题

本文以HDU2544为例：

• 题目大意
  给出一个带权无向图，求其从起点到终点的最短路径。

2.Dijkstra算法

• 算法思路
  Dijkstra算法算一种贪心算法，通过不断选择中间点找出起点到各个点的最短路（这个操作被称为松弛）。该算法常用于求单源图的最短路，具体见伪代码。
• 伪代码

  Dijkstra(){
  取邻接表起点行作为最短路记录数组；
  标记起点为已访问；
  以下操作循环次数为点的个数{
      找出最短路数组中未被访问的对应值最小的点并记录值为最小值，点位松弛点；
      标记最小值点为已访问；
      对所有最短路数组中的点{
          当前值与精工松弛点路径值中的较小值为新的最短路径值；
      }
  }
  }

• 实现（HDU2544）

  #include<iostream>
  #include<cmath>
  #include<cstdio>
  #include<sstream>
  #include<cstdlib>
  #include<string>
  #include<cstring>
  #include<algorithm>
  #include<vector>
  #include<map>
  #include<set>
  #include<stack>
  #include<list>
  #include<queue>
  #include<ctime>
  #include<bitset>
  #include<cmath>
  #define eps 1e-6
  #define INF 0x3f3f3f3f
  #define PI acos(-1.0)
  #define M 1000000007
  using namespace std;
  typedef long long LL;
  const int maxn = 105;
  int adj[maxn][maxn];
  int dis[maxn];
  bool vis[maxn];
  void init(int n)
  {
  memset(vis,false,sizeof(vis));
  memset(adj,INF,sizeof(adj));
  memset(dis,INF,sizeof(dis));
  for(int i = 1;i <= n;++i)
      adj[i][i] = 0;
  }
  int dijkstra(int n)
  {
  int minn,tmp; //最短路径值与松弛点
  for(int i = 1;i <= n;++i)
      dis[i] = adj[1][i];
  vis[1] = true;
  for(int i = 1;i <= n;++i)
  {
      minn = INF;
      for(int j = 1;j <= n;++j)
          if(!vis[j] && minn > dis[j])
          {
              tmp = j;
              minn = dis[j];
          }
      if(minn == INF)
          break;
      vis[tmp] = true;
      for(int j = 1;j <= n;++j)
          dis[j] = min(dis[j],dis[tmp] + adj[tmp][j]);
  }
  return dis[n];
  }
  int main()
  {
  int n,m;
  while(~scanf("%d%d", &n, &m) && n && m)
  {
      init(n);
      int st,ed,l;
      for(int i = 1;i <= m;++i)
      {
          scanf("%d%d%d", &st, &ed, &l);
          adj[st][ed] = l; //注意本体是无向图，要使邻接表对称
          adj[ed][st] = l;
      }
      int ans = dijkstra(n);
      printf("%d\n", ans);
  }
  
  return 0;
  }

  C++

  Copy

3.Floyd算法

• 算法思路
  个人认为，Floyd算法是一种dp算法，遍历每个点作为中间点的情况下另外每两个点间的路径，不断取最小值。这个过程过于简单，但是很暴力，时间复杂度高达O(n^3)，通常用于求多源最短路。由于过程过于简单，故本文不给伪代码。

• 实现（HDU2544）

  #include<iostream>
  #include<cmath>
  #include<cstdio>
  #include<sstream>
  #include<cstdlib>
  #include<string>
  #include<cstring>
  #include<algorithm>
  #include<vector>
  #include<map>
  #include<set>
  #include<stack>
  #include<list>
  #include<queue>
  #include<ctime>
  #include<bitset>
  #include<cmath>
  #define eps 1e-6
  #define INF 0x3f3f3f3f
  #define PI acos(-1.0)
  #define M 1000000007
  using namespace std;
  typedef long long LL;
  const int maxn = 105;
  int dp[maxn][maxn];
  int floyd(int n)
  {
  for(int tran = 1;tran < n;++tran) //遍历中转点
      for(int i = 1;i <= n;++i)
          for(int j = 1;j <= n;++j)
              dp[i][j] = min(dp[i][j],dp[i][tran] + dp[tran][j]); // i到j的最短路
                 return dp[1][n];
  }
  int main()
  {
  int n,m;
  while(~scanf("%d%d", &n, &m) && n && m)
  {
      int st,ed,l;
      memset(dp,INF,sizeof(dp));
      for(int i = 1;i <= n;++i)
          dp[i][i] = 0;
      for(int i = 1;i <= m;++i)
      {
          scanf("%d%d%d", &st, &ed, &l);
          dp[st][ed] = l;
          dp[ed][st] = l;
      }
      int ans = floyd(n);
      printf("%d\n", ans);
  }
  
  return 0;
  }

  C++

  Copy

说明：最短路算法还有SPFA算法和Bellman_Ford算法，教材中没有做要求，本文就不写了。（其实是我忘了）（蔡得真实）考完后找时间再写。

总提纲：《数据结构》期末复习提纲小结