33-算法解析及优化拓展

2.5.6　算法解析及优化拓展

1．算法时间复杂度

（1）时间复杂度：在Dijkstra算法描述中，一共有4个for语句，第①个for语句的执行次数为n，第②个for语句里面嵌套了两个for语句③、④，它们的执行次数均为n，对算法的运行时间贡献最大，当外层循环标号为1时，③、④语句在内层循环的控制下均执行n次，外层循环②从1～n。因此，该语句的执行次数为n*n= n²，算法的时间复杂度为O(n²)。

（2）空间复杂度：由以上算法可以得出，实现该算法所需要的辅助空间包含为数组flag、变量i、j、t和temp所分配的空间，因此，空间复杂度为O(n)。

2．算法优化拓展

在for语句③中，即在集合V−S中寻找距离源点u最近的顶点t，其时间复杂度为O(n)，如果我们使用优先队列，则可以把时间复杂度降为O(log n)。那么如何使用优先队列呢？

（1）优先队列（见附录C）

（2）数据结构

在上面的例子中，我们使用了一维数组dist[t]来记录源点u到顶点t的最短路径长度。在此为了操作方便，我们使用结构体的形式来实现，定义一个结构体Node，里面包含两个成员：u为顶点，step为源点到顶点u的最短路径。

struct  Node{
     int v,step; // v为顶点，step为源点到顶点v的最短路径
     Node(){};
     Node(int a,int sp){
         v = a;   //参数传递，v为顶点
         step = sp; //参数传递，step为源点到顶点v的最短路径
     }
     bool operator < (const  Node& a)const{ 
         return step > a.step; //重载 <，step(源点到顶点v的最短路径)最小值优先
     }
};

上面的结构体中除了两个成员变量外，还有一个构造函数和运算符优先级重载，下面详细介绍其含义用途。

为什么要使用构造函数？

如果不使用构造函数也是可以的，只定义一般的结构体，里面包含两个参数：

struct  Node{
     int v,step; // v为顶点，step为源点到顶点v的最短路径
};

那么在变量参数赋值时，需要这样赋值：

Node vs ; //先定义一个Node结点类型变量
vs.v =3 ,vs.step = 5; //分别对该变量的两个成员进行赋值

采用构造函数的形式定义结构体：

struct  Node{
     int u,step;
     Node(){};
     Node(int a,int sp){
         u = a;   //参数传递u为顶点
         step = sp; //参数传递step为源点到顶点u的最短路径
     }
};

则变量参数赋值就可以直接通过参数传递：

Node vs(3,5)

上面语句等价于：

vs.v =3 ,vs.step = 5;

很明显通过构造函数的形式定义结构体，参数赋值更方便快捷，后面程序中会将结点压入优先队列：

priority_queue <Node> Q;  // 创建优先队列，最小值优先
Q.push(Node(i,dist[i])); //将结点Node压入优先队列Q
                         //参数i传递给顶点v， dist[i]传递给step

（3）使用优先队列优化的Dijkstra算法源代码：

//program 2-5
#include <queue>
#include <iostream>
#include<cstring>
#include<windows.h>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 无穷大
int map[N][N],dist[N],n,m;
int flag[N];
struct  Node{
     int u,step;
     Node(){};
     Node(int a,int sp){
         u=a;step=sp;
     }
     bool operator < (const  Node& a)const{  // 重载 <
          return step>a.step;
     }
};
void Dijkstra(int st){
     priority_queue <Node> Q;  // 优先队列优化
     Q.push(Node(st,0));
     memset(flag,0,sizeof(flag));//初始化flag数组为0
     for(int i=1;i<=n;++i)
       dist[i]=INF; // 初始化所有距离为，无穷大
     dist[st]=0;
     while(!Q.empty())
     {
          Node it=Q.top();//优先队列队头元素为最小值
          Q.pop();
          int t=it.u;
          if(flag[t])//说明已经找到了最短距离，该结点是队列里面的重复元素
               continue;
          flag[t]=1;
          for(int i=1;i<=n;i++)
          {
              if(!flag[i]&&map[t][i]<INF){ // 判断与当前点有关系的点，并且自己不能到自己
                  if(dist[i]>dist[t]+map[t][i])
                  {   // 求距离当前点的每个点的最短距离,进行松弛操作
                      dist[i]=dist[t]+map[t][i];
                      Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列，注意：里面的元素有重复
                  }
              }
          }
     }
}
int main()
{
          int u,v,w,st;
          system("color 0d");//设置背景及字体颜色
          cout << "请输入城市的个数："<<endl;
          cin >> n;
          cout << "请输入城市之间的路线的个数："<<endl;
          cin >>m;
          for(int i=1;i<=n;i++)//初始化图的邻接矩阵
             for(int j=1;j<=n;j++)
             {
                 map[i][j]=INF;//初始化邻接矩阵为无穷大
             }
          cout << "请输入城市之间u,v的路线以及距离w："<<endl;
          while(m--)
          {
               cin>>u>>v>>w;
               map[u][v]=min(map[u][v],w); //邻接矩阵储存，保留最小的距离
          }
          cout<<"请输入小明所在的位置："<<endl; ;
          cin>>st;
          Dijkstra(st);
          cout <<"小明所在的位置："<<st<<endl;
          for(int i=1;i<=n;i++)
          {
               cout <<"小明:"<<st<<"--->"<<"要去的位置："<<i;
               if(dist[i]==INF)
                   cout << "sorry,无路可达"<<endl;
               else
                   cout << " 最短距离为："<<dist[i]<<endl;
          }
     return 0;
}

算法实现和测试

（1）运行环境

Code::Blocks

（2）输入

请输入城市的个数：
5
请输入城市之间的路线的个数：
7
请输入城市之间的路线以及距离：
1 2 2
1 3 3 
2 3 5
2 4 6
3 4 7
3 5 1
4 5 4
请输入小明所在的位置：
1

（3）输出

小明所在的位置：1
小明：1 - 要去的位置：1 最短距离为：0
小明：1 - 要去的位置：2 最短距离为：2
小明：1 - 要去的位置：3 最短距离为：3
小明：1 - 要去的位置：4 最短距离为：8
小明：1 - 要去的位置：5 最短距离为：4

在使用优先队列的 Dijkstra 算法描述中，while (!Q.empty())语句执行的次数为n，因为要弹出n个最小值队列才会空；Q.pop()语句的时间复杂度为logn，while语句中的for语句执行n次，for语句中的Q.push (Node(i,dist[i]))时间复杂度为logn。因此，总的语句的执行次数为n logn+n²logn，算法的时间复杂度为O(n²logn)。

貌似时间复杂度又变大了？

这是因为我们采用的邻接矩阵存储的，如果采用邻接表存储（见附录D），那么for语句④松弛操作就不用每次执行n次，而是执行t结点的邻接边数x，每个结点的邻接边加起来为边数E，那么总的时间复杂度为O(nlogn+Elogn)，如果En，则时间复杂度为O(E*logn)。

注意： 优先队列中尽管有重复的结点，但重复结点最坏是n²，log n²=2 log n，并不改变时间复杂度的数量级。

想一想，还能不能把时间复杂度再降低呢？如果我们使用斐波那契堆，那么松弛操作的时间复杂度O(1)，总的时间复杂度为O(n* logn+E)。