数据结构 第15讲 一场说走就走的旅行——最短路径

一场说走就走的旅行——最短路径

本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

有一天,孩子回来对我说:“妈妈,听说马尔代夫很不错,放假了我想去玩。”马尔代夫?我也想去!没有人不向往一场说走就走的旅行!“其实我想去的地方很多,呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图,标出想去的地点,然后计算最短路线,估算大约所需的时间,有了这张秘制地图,一场说走就走的旅行不是梦!

“哇,感觉我们像凡尔纳的《环游地球八十天》,好激动!可是老妈你也太out了,学计算机的最短路线你用手算?”

暴汗……,“小子你别牛,你知道怎么算?”

“呃,好像是叫什么迪科斯彻的人会算。”

哈哈,关键时刻还要老妈上场了!

图2-8 一场说走就走的旅行

2.5.1 问题分析

根据题目描述可知,这是一个求单源最短路径的问题。给定有向带权图G =(V,E),其中每条边的权是非负实数。此外,给定V中的一个顶点,称为源点。现在要计算从源到所有其他各顶点的最短路径长度,这里路径长度指路上各边的权之和。

如何求源点到其他各点的最短路径呢?

如图2-9所示,艾兹格•W•迪科斯彻(Edsger Wybe Dijkstra),荷兰人,计算机科学家。他早年钻研物理及数学,后转而研究计算学。他曾在1972年获得过素有“计算机科学界的诺贝尔奖”之称的图灵奖,与Donald Ervin Knuth并称为我们这个时代最伟大的计算机科学家。

图2-9 艾兹格•W•迪科斯彻

2.5.2 算法设计

Dijkstra 算法是解决单源最短路径问题的贪心算法,它先求出长度最短的一条路径,再参照该最短路径求出长度次短的一条路径,直到求出从源点到其他各个顶点的最短路径。

Dijkstra算法的基本思想是首先假定源点为u,顶点集合V被划分为两部分:集合S和 V−S。初始时 S 中仅含有源点 u,其中 S 中的顶点到源点的最短路径已经确定。集合V−S中所包含的顶点到源点的最短路径的长度待定,称从源点出发只经过S中的点到达V−S中的点的路径为特殊路径,并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径,将其连接的V−S中的顶点加入到集合S中,同时更新数组dist[]。一旦S包含了所有顶点,dist[]就是从源到所有其他顶点之间的最短路径长度。

(1)数据结构。设置地图的带权邻接矩阵为map[][],即如果从源点u到顶点i有边,就令 map[u][i]等于<u,i>的权值,否则 map[u][i]=∞(无穷大);采用一维数组 dist[i]来记录从源点到i顶点的最短路径长度;采用一维数组p[i]来记录最短路径上i顶点的前驱。

(2)初始化。令集合S={u},对于集合V−S中的所有顶点x,初始化dist[i]=map[u][i],如果源点u到顶点i有边相连,初始化p[i]=u,否则p[i]= −1。

(3)找最小。在集合V−S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t,即dist[t]=min(dist[j]|j属于V−S集合),则顶点t就是集合V−S中距离源点u最近的顶点。

(4)加入S战队。将顶点t加入集合S中,同时更新V−S。

(5)判结束。如果集合V−S为空,算法结束,否则转(6)。

(6)借东风。在(3)中已经找到了源点到t的最短路径,那么对集合V−S中所有与顶点t相邻的顶点j,都可以借助t走捷径。如果dis[j]>dist[t]+map[t][j],则dist[j]=dist[t]+map[t][j],记录顶点j的前驱为t,有p[j]= t,转(3)。

由此,可求得从源点u到图G的其余各个顶点的最短路径及长度,也可通过数组p[]逆向找到最短路径上经过的城市。

2.5.3 完美图解

现在我们有一个景点地图,如图2-10所示,假设从1号结点出发,求到其他各个结点的最短路径。

图2-10 景点地图

算法步骤如下。

(1)数据结构

设置地图的带权邻接矩阵为map[][],即如果从顶点i到顶点j有边,则map[i][j]等于<i,j>的权值,否则map[i][j]=∞(无穷大),如图2-11所示。

图2-11 邻接矩阵map[][]

(2)初始化

令集合S={1},V−S={2,3,4,5},对于集合V−S中的所有顶点x,初始化最短距离数组dist[i]=map[1][i],dist[u]=0,如图2-12所示。如果源点1到顶点i有边相连,初始化前驱数组p[i]=1,否则p[i]= −1,如图2-13所示。

图2-12 最短距离数组dist[]

图2-13 前驱数组p[]

(3)找最小

在集合V−S={2,3,4,5}中,依照贪心策略来寻找V−S集合中dist[]最小的顶点t,如图2-14所示。

图2-14 最短距离数组dist[]

找到最小值为2,对应的结点t=2。

(4)加入S战队

将顶点t=2加入集合S中S={1,2},同时更新V−S={3,4,5},如图2-15所示。

图2-15 景点地图

(5)借东风

刚刚找到了源点到t=2的最短路径,那么对集合V−S中所有t的邻接点j,都可以借助t走捷径。我们从图或邻接矩阵都可以看出,2号结点的邻接点是3和4号结点,如图2-16所示。

图2-16 邻接矩阵map[][]

先看3号结点能否借助2号走捷径:dist[2]+map[2][3]=2+2=4,而当前dist[3]=5>4,因此可以走捷径即2—3,更新dist[3]=4,记录顶点3的前驱为2,即p[3]= 2。

再看4号结点能否借助2号走捷径:如果dist[2]+map[2][4]=2+6=8,而当前dist[4]=∞>8,因此可以走捷径即2—4,更新dist[4]=8,记录顶点4的前驱为2,即p[4]= 2。

更新后如图2-17和图2-18所示。

图2-17 最短距离数组dist[]

图2-18 前驱数组p[]

(6)找最小

在集合V−S={3,4,5}中,依照贪心策略来寻找dist[]具有最小值的顶点t,依照贪心策略来寻找V−S集合中dist[]最小的顶点t,如图2-19所示。

图2-19 最短距离数组dist[]

找到最小值为4,对应的结点t=3。

(7)加入S战队

将顶点t=3加入集合S中S={1,2,3},同时更新V−S={4,5},如图2-20所示。

图2-20 景点地图

(8)借东风

刚刚找到了源点到t =3的最短路径,那么对集合V−S中所有t的邻接点j,都可以借助t走捷径。我们从图或邻接矩阵可以看出,3号结点的邻接点是4和5号结点。

先看4号结点能否借助3号走捷径:dist[3]+map[3][4]=4+7=11,而当前dist[4]=8<11,比当前路径还长,因此不更新。

再看5号结点能否借助3号走捷径:dist[3]+map[3][5]=4+1=5,而当前dist[5]=∞>5,因此可以走捷径即3—5,更新dist[5]=5,记录顶点5的前驱为3,即p[5]=3。

更新后如图2-21和图2-22所示。

图2-21 最短距离数组dist[]

图2-22 前驱数组p[]

(9)找最小

在集合V−S={4,5}中,依照贪心策略来寻找V−S集合中dist[]最小的顶点t,如图2-23所示。

图2-23 最短距离数组dist[]

找到最小值为5,对应的结点t=5。

(10)加入S战队

将顶点t=5加入集合S中S={1,2,3,5},同时更新V−S={4},如图2-24所示。

图2-24 景点地图

(11)借东风

刚刚找到了源点到t =5的最短路径,那么对集合V−S中所有t的邻接点j,都可以借助t走捷径。我们从图或邻接矩阵可以看出,5号结点没有邻接点,因此不更新,如图2-25和图2-26所示。

图2-25 最短距离数组dist[]

图2-26 前驱数组p[]

(12)找最小

在集合V−S={4}中,依照贪心策略来寻找dist[]最小的顶点t,只有一个顶点,所以很容易找到,如图2-27所示。

图2-27 最短距离数组dist[]

找到最小值为8,对应的结点t=4。

(13)加入S战队

将顶点t加入集合S中S={1,2,3,5,4},同时更新V−S={ },如图2-28所示。

图2-28 景点地图

(14)算法结束

V−S={ }为空时,算法停止。

由此,可求得从源点u到图G的其余各个顶点的最短路径及长度,也可通过前驱数组p[]逆向找到最短路径上经过的城市,如图2-29所示。

图2-29 前驱数组p[]

例如,p[5]=3,即5的前驱是3;p[3]=2,即3的前驱是2;p[2]=1,即2的前驱是1;p[1]= −1,1没有前驱,那么从源点1到5的最短路径为1—2—3—5。

2.5.4 伪代码详解

(1)数据结构

n:城市顶点个数。m:城市间路线的条数。map[][]:地图对应的带权邻接矩阵。dist[]:记录源点u到某顶点的最短路径长度。p[]:记录源点到某顶点的最短路径上的该顶点的前一个顶点(前驱)。flag[]:flag[i]等于true,说明顶点i已经加入到集合S,否则顶点i属于集合V−S。

const int N = 100; //初始化城市的个数,可修改
const int INF = 1e7; //无穷大
int map[N][N],dist[N],p[N],n,m;
bool flag[N];

(2)初始化源点u到其他各个顶点的最短路径长度,初始化源点u出边邻接点(t的出边相关联的顶点)的前驱为u:

bool flag[n];//如果flag[i]等于true,说明顶点i已经加入到集合S;否则i属于集合V-S
for(int i = 1; i <= n; i ++)
    {
      dist[i] = map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
      flag[i]=false;
      if(dist[i]==INF)
         p[i]=-1;   //说明源点u到顶点i无边相连,设置p[i]=-1
    else
         p[i]=u;   //说明源点u到顶点i有边相连,设置p[i]=u
    }

(3)初始化集合S,令集合S={u},从源点到u的最短路径为0。

flag[u]=true;   //初始化集合S中,只有一个元素:源点 u 
dist[u] = 0;   //初始化源点 u的最短路径为0,自己到自己的最短路径

(4)找最小

在集合V−S中寻找距离源点u最近的顶点t,若找不到t,则跳出循环;否则,将t加入集合S。

    int temp = INF,t = u ;
    for(int j = 1 ; j <= n ; j ++) //在集合V-S中寻找距离源点u最近的顶点t
      if( !flag[j] && dist[j] < temp)
      {
         t=j;   //记录距离源点u最近的顶点
         temp=dist[j];
      }
    if(t == u) return ; //找不到t,跳出循环
    flag[t] = true;      //否则,将t加入集合S

(5)借东风

考查集合V−S中源点u到t的邻接点j的距离,如果源点u经过t到达j的路径更短,则更新dist[j] =dist[t]+map[t][j],即松弛操作,并记录j的前驱为t:

for(int j = 1; j <= n; j ++)  //更新集合V-S中与t邻接的顶点到源点u的距离
   if(!flag[j] && map[t][j]<INF) //!flag[j]表示j在V-S中,map[t][j]<INF表示t与j邻接
      if(dist[j]>(dist[t]+map[t][j])) //经过t到达j的路径更短
      {
         dist[j]=dist[t]+map[t][j] ;
         p[j]=t; //记录j的前驱为t 
      }

重复(4)~(5),直到源点u到所有顶点的最短路径被找到。

2.5.5 实战演练

//program 2-4
#include <cstdio>
#include <iostream>
#include<cstring>
#include<windows.h>
#include<stack>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 初始化无穷大为10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数,m为城市间路线的条数
bool flag[N]; //如果flag[i]等于true,说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
   for(int i=1; i<=n; i++)//①
    {
     dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
     flag[i]=false;
     if(dist[i]==INF)
        p[i]=-1; //源点u到该顶点的路径长度为无穷大,说明顶点i与源点u不相邻
     else
        p[i]=u; //说明顶点i与源点u相邻,设置顶点i的前驱p[i]=u
     }
    dist[u] = 0;
    flag[u]=true;   //初始时,集合S中只有一个元素:源点u
    for(int i=1; i<=n; i++)//②
     {
         int temp = INF,t = u;
         for(int j=1; j<=n; j++) //③在集合V-S中寻找距离源点u最近的顶点t
           if(!flag[j]&&dist[j]<temp)
             {
              t=j;
              temp=dist[j];
             }
           if(t==u) return ; //找不到t,跳出循环
           flag[t]= true;  //否则,将t加入集合
           for(int j=1;j<=n;j++)//④//更新集合V-S中与t邻接的顶点到源点u的距离
             if(!flag[j]&& map[t][j]<INF)//!flag[j]表示j在V-S中  
                if(dist[j]>(dist[t]+map[t][j]))
                 {
                   dist[j]=dist[t]+map[t][j] ;
                   p[j]=t ;
                 }
             }
     }
     int main()
     {
             int u,v,w,st;
             system("color 0d");
             cout << "请输入城市的个数:"<<endl;
             cin >> n;
             cout << "请输入城市之间的路线的个数:"<<endl;
             cin >>m;
             cout << "请输入城市之间的路线以及距离:"<<endl;
             for(int i=1;i<=n;i++)//初始化图的邻接矩阵
               for(int j=1;j<=n;j++)
               {
                   map[i][j]=INF;//初始化邻接矩阵为无穷大
               }
             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<<endl;
                   if(dist[i] == INF)
                      cout << "sorry,无路可达"<<endl;
                   else
                      cout << "最短距离为:"<<dist[i]<<endl;
             }
             return 0;
   }

算法实现和测试

(1)运行环境

Code::Blocks

(2)输入

请输入城市的个数:
5
请输入城市之间的路线的个数:
11
请输入城市之间的路线以及距离:
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入小明所在的位置:
5

(3)输出

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

想一想:因为我们在程序中使用p[]数组记录了最短路径上每一个结点的前驱,因此除了显示最短距离外,还可以显示最短路径上经过了哪些城市,可以增加一段程序逆向找到该最短路径上的城市序列。

void findpath(int u)
{
  int x;
  stack<int>s;//利用C++自带的函数创建一个栈s,需要程序头部引入#include<stack>
  cout<<"源点为:"<<u<<endl;
  for(int i=1;i<=n;i++)
  {
    x=p[i];
    while(x!=-1)
    {
      s.push(x);//将前驱依次压入栈中
      x=p[x];
    }
    cout<<"源点到其他各顶点最短路径为:";
    while(!s.empty())
    {
      cout<<s.top()<<"--";//依次取栈顶元素
      s.pop();//出栈
    }
    cout<<i<<";最短距离为:"<<dist[i]<<endl;
  }
}

只需要在主函数末尾调用该函数:

findpath(st);//主函数中st为源点

输出结果如下。

源点为:5
源点到其他各顶点最短路径为:5--1;最短距离为:8
源点到其他各顶点最短路径为:5--1--2;最短距离为:24
源点到其他各顶点最短路径为:5--1--3;最短距离为:23
源点到其他各顶点最短路径为:5--1--3--4;最短距离为:30
源点到其他各顶点最短路径为:5;最短距离为:0

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

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

为什么要使用构造函数?

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

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

那么在变量参数赋值时,需要这样赋值:

Node vs ; //先定义一个Node结点类型变量
vs.u =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传递给顶点u, 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(n*logn+E*logn),如果E>=n,则时间复杂度为O(E*logn)。

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

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

契堆,那么松弛操作的时间复杂度O(1),总的时间复杂度为O(n* logn+E)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏javascript趣味编程

5.2.1 二维导热算例-热导的概念

材料类,描述材料的参数,如密度、比热和初始温度等,这里特别给出了凝固潜热;这里要注意Math.pow(2,0)的意义,读者自己琢磨,用于判断相邻控制体的...

11900
来自专栏应兆康的专栏

100个Numpy练习【5】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

818120
来自专栏数据结构与算法

2843 拯救炜哥

2843 拯救炜哥 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有一天,炜...

29450
来自专栏云时之间

NLP入门之形式语言与自动机学习(二)

1:什么是命题? 说起什么是命题,命题是一个能够判断真假的语句,一般可以用一个大写的字母表示为一个命题.举个例子:

43260
来自专栏数据结构与算法

网络流应用

刷了一天最大流的题,都快刷晕了,, 简单总结几个模型吧。 大部分内容来自学姐的PPT 拆点 一个非常有用的思想 限流 将对点的限制转化为对边的限制 点的合并 ...

43190
来自专栏PPV课数据科学社区

【学习】笨办法学R编程(四)

随着教程推进,基本的语法都接触得差不多了。当要解决某个具体问题时,只需要考虑用什么样的算法来整合运用这些函数和表达式。今天来解决Project ...

29240
来自专栏灯塔大数据

每周学点大数据 | No.15 图在计算机中的存储

No.15期 图在计算机中的存储 Mr. 王:还有一个很重要的问题,就是图在计算机中的表示。虽然我们看到的图边和点等都是非常直观的,可以画成一个圆圈里带一个数...

37570
来自专栏JadePeng的技术博客

从编辑距离、BK树到文本纠错

搜索引擎里有一个很重要的话题,就是文本纠错,主要有两种做法,一是从词典纠错,一是分析用户搜索日志,今天我们探讨使用基于词典的方式纠错,核心思想就是基于编辑距离,...

70760
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

11930
来自专栏开发与安全

算法:堆栈与深度优先搜索(迷宫问题)

堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能...

37890

扫码关注云+社区

领取腾讯云代金券