关于如何在ubuntu14.04以上的64位系统中使用32位的Dr.com上网。

当时因为64位不能使用校园网上网，所以导致整个实验室的Linux都用的32位。现在终于解决了这个问题。

1 download spark-bin

在apache官网下载spark1.3.1-bin-hadoop-2.6.tgz地址如下:

“http://spark.apache.org/downloads.html“

2 配置spark集群

承接上一篇文章，我们将spark文件放在/usr/local/bigdata/spark下。
并且在.bashrc中配置spark的环境变量。

hadoop2.6.0集群搭建-ubuntu14.04

这一周实习做的是百度地图，所以要用到各个城市的经纬度来进行查询。百度了许久后找到一份几年前的记录。那时晋州还叫晋县，武穴还叫广济。现在先记录下来。

因为需要搭建一个集群，所以需要安装多台虚拟机进行。Vmware太大而且是收费的，所以最后决定用virtualbox.

在过程中遇到了如下问题:

Kernel driver not installed (rc=-1908)

The VirtualBox Linux kernel driver (vboxdrv) is either not loaded or there is a permission problem with /dev/vboxdrv. Please reinstall the kernel module by executing

‘/etc/init.d/vboxdrv setup’

as root. If it is available in your distribution, you should install the DKMS package first. This package keeps track of Linux kernel changes and recompiles the vboxdrv kernel module if necessary.

下面就说一下安装的流程。

spfa算是是使用队列去优化bellman的一种算法吧。

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。

以前说的都是不存在负环的最短路径算法，但是如果一旦边的权值出现负数，则循环将无限进行。所以我们需要一种算法来判断是否出现负环。

下面就简单介绍一下Bellman-ford 算法。

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

说的好厉害的样子，其实就是求有向图中单源最短路径的问题。

其实理解floyd或者贪心最小生成树后，应该很容易理解这个算法的。

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。

此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。Robert W．Floyd这个牛人是朵奇葩，他原本在芝加哥大学读的文学，但是因为当时美国经济不太景气，找工作比较困难，无奈之下到西屋电气公司当了一名计算机操作员，在IBM650机房值夜班，并由此开始了他的计算机生涯。

本周题目主要是联系最短路径的几个算法。主要是floyd,dijkstra和Bellman-Ford,最后一题也可以用spfa.

这些算法会重新利用其他文章去解释。

简单说一下这些算法的用法。

floyd是用来计算图中任意一点到其他点的最短路径。写起来也比较简单，时间复杂度为O(n^3).

dijkstra是计算单源最短路径的算法，也就是相当于固定了起点。所以时间复杂度降为O(n^2).

以上两个算法面临权值为负时便无法正常的运行下去，所以为了处理出现负环等情况。使用下面的算法。
Bellman-Ford简单暴力的处理相关问题，没有做任何优化。写起来很简单，用起来也不错。时间复杂度大概为O(ne).
spfa一般是在上面的基础上加上了队列，有的好像加的是优先队列。反正就是效率大大提高就对了。时间复杂度为O(ek).据说k很小。其实我并不知道有多小。