最短路径算法 假设图G(V,E), 有n个顶点，e条边，w(u,v)为两点间边的权值，这里分别介绍两种单源点和两种多源点最短路径算法
Dijkstra是典型的最短路径算法，不允许有负权边存在。算法采用的是贪婪算法，普通方法实现的话，时间复杂度为O(n^2),但可以用最小优先队列或者堆实现，可以将时间复杂度降为O(e + nlog(n)) , 这样的算法速度比bellman算法要快。
首先假设几个变量并初始化：
算法步骤：
该算法可以有效快速的求解单源点最短路径问题适用范围：
首先假设几个变量：
关于松弛计算概念：
对某一条边e(u,v)，如果 d(v) > d(u) + w(u,v)，则 d(v) = d(u) + w(u,v)
算法步骤:
由上述算法可以发现，这个算法的时间复杂度是O(ne), 而且源点到各点的距离要等到最后循环完成之后才能确定。
计算有向图中任意两点之间的距离,可以认为是对单源最短路径的推广
该算法理解起来比较简单， 就是通过检查每条边来确定这条边是不是更短路径的一部分，适用范围：
算法伪码步骤：
初始化：
dist[i][j] = 0, if i=j;
= w[i][j], if i!=j and e(i,j) in E;
= infinite , if i!=j and e(i,j) not in E;
计算最短路径：
for k=1 to n
for i=1 to n
for j=1 to n
if( dist[i][k] + dist[k][j] ) < dist[i][j]
dist[i][j] = dist[i][k] + dist[k][j]
以上可知，该算法也是贪婪算法，时间复杂度为 O(n^3)，所以效率比较低
适用范围：
该算法想法比较奇妙，考虑利用bellmanford算法和dijkstra算法，因此需要先加入了一个点到原图。还采用了reweighting的思想，由于Dijkstra算法不允许负权边存在，需要reweighting所有权边，如果G有负权边， reweighting之后所有的边都是非负权边
算法步骤:
这个算法看起来比较复杂，但是其实效率比较高，步骤1的时间复杂度是O(n),步骤2的是O(ne),步骤3的是O(e),步骤4的则是O(enlogn)，步骤5的是O(n^2)，则最终这个算法的时间复杂度是O(enlogn)，比floyd的效率要高。
冒泡排序，依序比较相邻的两个，顺序不对则交换
时间复杂度 O(n^2)
void bsort(int a[], n){
for(int i=0; i<n; i++){
for(int j=0; j<n-i-1; j++){
if(a[j]>a[j+1]){
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
选择排序，从第一个元素开始往后遍历，每轮从后面选择最小的元素排到最前面。
时间复杂度 O(n^2),排序速度先慢后快，因为要查找的元素的元素逐个减少。大量查找，少量移动。
void selectsort(int a[], n ){
for(int i=0; i<n; i++){
min = a[i];
for(int j = i+1; j<n; j++){
if(a[j]<min){
int temp;
temp = min;
min = a[j];
a[j] = temp;
}
}
a[i] = min;
}
}
将序列分为已排序和未排序两个部分，对未排序部分依序遍历插入前面已排序部分。
先快后慢。后几轮插入时要比较的更多。
依序对后面的n-1个元素遍历，
for i in 1 - n:
将第i个元素插入前面i-1个已排序元素中
void insertionsort(int a[], int n ){
for(int i=1; i<n; i++){
int temp = a[i];
for(int j=i-1;j>=0;j--){
if(a[j]>temp)
a[j+1] = a[j];
else{
a[j+1] = temp;
break;
}
}
}
}
归并排序要调用递归的方法,步骤：
时间复杂度 O(nlogn)，空间上需要额外的 n 个空间，不利于基本有序的序列。
void merge(int a[], int low, int mid, int high, int temp[]){
int i =low;
int j = mid+1;
int k =0;
while(i <=mid && j<=high){
if(a[i]<a[j]){
temp[k++]=a[i];
i++;
}
else{
temp[k++]=a[j];
j++;
}
}
while(i<=mid){
temp[k++] = a[i];
i++;
}
while(j<=high) {
temp[k++] = a[j];
j++;
}
for(int i=0; i<k; i++){
a[i+low] = temp[i];
}
}
void mergesort(int a[], int low, int high, int temp[] ){
if(low<high){
int mid = (high+low)/2;
mergesort(a, low, mid,temp);
mergesort(a, mid+1, high,temp);
merge(a, low, mid, high,temp);
}
}
也是要用到递归
时间复杂度 O(nlogn)，相对归并排序不需要额外的空间，p 的选择对排序影响比较大，序列基本有序时会相对快。
int partition(int a[], int low, int high){
int midvalue = a[low];
int i = low;
int j = high;
while(i<j){
while(a[j]>midvalue && i<j)
j--;
if(i<j)
a[i++] = a[j];
while(a[i]<midvalue && i<j)
i++;
if(i<j)
a[j--] = a[i];
}
a[i]=midvalue;
return i;
}
void quicksort(int a[], int low, int high){
if(low<high){
int pivot = partition(a, low, high);
quicksort(a, low, pivot-1);
quicksort(a, pivot+1, high);
}
}
大根堆： 父节点比两个子节点都大，小根堆反之。
//调整以第i个节点为父节点的树，使之成为大根堆
int adjust_heap(vector<int> &v, int length, int i){
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
int temp;
while(left < length || right < length){
if (left < length && v[largest] < v[left]){
largest = left;
}
if (right < length && v[largest] < v[right]){
largest = right;
}
if (i != largest){
temp = v[largest];
v[largest] = v[i];
v[i] = temp;
i = largest;
left = 2 * i;
right = 2 * i + 1;
}
else{
break;
}
}
}
//建立堆，使首节点最大。从最后一个非叶子节点开始，逐个向前，调整为大根堆
int build_heap(vector<int> &v, int length){
int i;
int begin = length/2 - 1; //get the last parent node
for (i = begin; i>=0; i--){
adjust_heap(v,length,i);
}
}
int heap_sort(vector<int> &v){
int length = v.size();
int temp;
build_heap(v,length);
for(int i=n-1;i>=0;i--)
//交换v[0]和v[i]
temp = v[i];
v[i] = v[0];
v[0] = temp;
i--;
//调正前 i-1 个元素是大根堆来获取前i-1的最大值
adjust_heap(v,i,0);
}
}
其实就是分段的插入排序