Algorithm-Bellman_Ford

算法核心:对包含任意边的集合U,其中w(p, n)表示从点p到点n的权重,d(p)表示从起始点到点p的权重。则,有松弛操作,当:

d(n) > w(p, n) + d(p)

时,则更新:

d(n) = w(p, n) + d(p)

所以,松弛操作的作用就是为了更新从起始点到点n的权值,使其趋向最小。

这里举个例子,目前有有向图,设为集合E,表示如下(下方中infinite表示为无穷大的数):
A->B:-3;
B->C:2;
C->D:3;
D->E:2;
A->E:5;
接下来进行,|V|-1轮的松弛操作,因为图的最短路径最长不会经过超过 |V|-1条边,这里的|V|代表的节点的数量。
设起始点为A,则初始化点A到点A,B,C,D,E的距离,设为集合U,表示为:
A->A:0;
A->B:infinite;
A->C:infinite;
A->D:infinite;
A->E:infinite;
第一次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;{d(B) > w(A, B) + d(A) => infinite > 0 + (-3),执行更新}
A->C:infinite;
A->D:infinite;
A->E:5;{d(E) > w(A, E) + d(E) => infinite > 0 + 5,执行更新}
第二次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;{d(C) > w(B, C) + d(B) => infinite > (-3) + 2,执行更新}
A->D:infinite;
A->E:5;
第三次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;
A->D:2;{d(D) > w(C, D) + d(C) => infinite > -1 + 3, 执行更新}
A->E:5;
第四次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;
A->D:2;
A->E:4;{d(E) > w(D, E) + d(D) => 5 > 2 + 2,执行更新}
完成所有4轮松弛操作,得到A到各个节点的最优解。

这里会发现一个问题,如果有负权环怎么办。负权环的存在会导致在该权环中的值可以无限的小。所以这里直接可以进行一个简单的判断,判断进行n-1轮(n表示节点数量)后该图是否还存在可以进行松弛操作的点,如果存在,即表示该图中存在负权环,没有解。

Python3代码实现:

Add New Extension For PHP

环境:CentOS 7,PHP 7.3.9

这里介绍一个给php单独添加扩展的方式。针对通过源码编译的php。这里是安装intl扩展。intl需要有icu。

1.先安装icu,下载icu源码包(下载地址:http://site.icu-project.org/):wget https://github.com/unicode-org/icu/releases/download/release-64-2/icu4c-64_2-src.zip

2.解压icu4c-64_2-src.zip:unzip icu4c-64_2-src.zip

3.进入icu源码目录:cd icu/source

4.配置icu安装目录:./configure –prefix=/usr/local/icu

5.执行编译:make && make install

安装好icu后,安装intl:
1.获取intl(如果你是源码安装的话,并且没有删除源码包,那么可以在源码包中找到intl,位置在源码包目录下的ext目录中;如果没有的话也没关系,从网络上获取http://pecl.php.net/get/intl-3.0.0.tgz):wget http://pecl.php.net/get/intl-3.0.0.tgz

2.解压intl.tgz文件:tar -zxvf intl-3.0.0.tgz

3.进入intl目录:cd intl-3.0.0

4.运行phpize命令(这是一个可以将临时想添加的扩展添加到php中。ps.它不是自动添加的,还是要手动):phpize

5.配置intl:./configure –enable-intl –with-icu-dir=/usr/local/icu –with-php-config=/usr/local/php/bin/php-config

6.开始进行源码编译:make && make install

7.将编译后的扩展添加到php.ini中(php.ini的目录:通过php -i | grep php.ini命令查看):vim php.ini

8.找到有一大堆extension的地方,写入extension intl.so,格式跟其它extension写法相同,对于不同的安装方式intl.so的位置不同,可以使用绝对路径添加。

9.重启php(因为我这里有php-fpm):systemctl restart php-fpm

10.通过php-fpm查看该模块是否安装上去(安装上去的话会显示出来,也可以通过浏览器访问phpinfo页面的方式):php-fpm -m

Gogs: Build Your Private Repositories

搭建个人代码存储库
环境:CentOS 7.3,mysql 5.7

1.首先安装git:yum install -y git
2.查看git版本:git –version
3.添加用户组:groupadd git
4.添加用户:useradd -g git git
5.修改密码:passwd git
6.切换到git用户:su git
7.到git的家目录:cd ~

数据库的安装不再做赘述。

获取gogs(gogs包的地址: https://dl.gogs.io):
1.wget -c “https://dl.gogs.io/0.11.86/gogs_0.11.86_linux_amd64.zip” -O gogs.zip
2.解压:unzip gogs.zip
3.进入gogs的目录:cd gogs
4.运行命令:./gogs web,通过浏览器: “ip:端口号” 即可访问gogs。默认端口为3000

gogs挂起(即使断开ssh的连接,它也会运行,不过关机或者重启后需要重新运行该命令):nohup ./gogs web &

nginx的反向代理到二级域名:比如域名为gogs.fixbugs.cn
1.编辑nginx的配置文件nginx.conf(具体文件位置依安装方式而定):vim /etc/nginx/nginx.conf
2.再nginx.conf中的http块的最下方添加:include /etc/nginx/conf.d/*.conf;

3.在/etc/nginx/conf.d/下写配置文件(命名方式xxx.conf):vim /etc/nginx/conf.d/gogs.conf内容如下:

4.保存退出后,nginx -s reload就可以通过域名访问gogs.