【图】最小路径

最小路径问题描述：

在一个(有向/无向)图中，每个结点间存在或不存在直接路径(不经过其他结点直接到达结点的路径)，每条路径上拥有其权值，寻找一条路径，使得v0->vk所经过的路径权值之和最小。

图1

上面是一个无向图，对于上面的图，可以确定一个图的二维矩阵(即邻接矩阵)，行首为起始结点，列首为目标结点。

起始/目标	v0	v1	v2	v3	v4	v5
v0	0	2	1	5	-1	-1
v1	2	0	2	3	1	-1
v2	1	2	0	3	1	2
v3	5	3	3	0	1	5
v4	-1	1	1	1	0	2
v5	-1	-1	2	5	2	0

注意：无向图是一个对称矩阵，有向图大多都不是对称矩阵，0表示起始结点与目标结点相同，-1表示无法到达。

分析：

(1).迪杰斯特拉算法-Dijkstra

图片摘自http://blog.csdn.net/todd911/article/details/9347053

图2

①所有结点为集合v的元素，假设当前已知最小路径的结点集合为s，m[j]表示从v0->vi->vj的最短路径，表示为min{v0->vi->vj}（注意：v0->v0->vj=v0->vj），其中vi∈s，vj∈v-s，那么将m[x]中最小值对应的vj加入集合s。

如图1所示v={v0,v1,v2,v3,v4,v5}，s={v0}，计算min{v0->vj}m={0,2,1,∞,5,∞}，

此时将v2加入集合s，s={v0,v2}，比较m与min{v0->v2->vj}相应结点的值，并将m中的值替换成较小值，此时m={0,2,1,2,4,3}；

此时将v1加入集合s，s={v0,v2,v1}，比较m与min{v0->v1->vj}相应结点的值，并将m中的值替换成较小值，此时m={0,2,1,2,4,3}；

此时将v3加入集合s，s={v0,v2,v1,v3}，比较m与min{v0->v3->vj}相应结点的值，并将m中的值替换成较小值，此时m={0,2,1,2,3,3}；

此时将v4加入集合s，s={v0,v2,v1,,v4}，比较m与min{v0->v4->vj}相应结点的值，并将m中的值替换成较小值，此时m={0,2,1,2,3,3}；

此时将v5加入集合s，完毕。

②为何min{v0->vi->vj}中vi必须∈s?假设vp∉s，若v0->vp->vx<min{v0->vi->vj} (vi∈s，vj∉s且j=0,1,2...n，vx为vj的其中一个)，那么由于v0->vp<v0->vp->vx<min{v0->vi->vj}，所以此时，vp必将加入集合s中。所以与假设不符。

③使用path记录vj的前驱结点为vi，则算法结束后可以由path还原出具体路径。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void perror(char *str){
	printf("%s", str);
	system("pause");
	exit(0);
}

void input_graph_array(int **data, int *n){
	int i,j;

	scanf("%d", n);
	*data = (int*)malloc(sizeof(int)*(*n)*(*n));
	if(*data==NULL)
		perror("malloc failed
");
	
	for(i=0; i<*n; i++){
		for(j=0; j<*n; j++){
			if(j==0)
				scanf("%d", *data+i*(*n));
			else
				scanf(" %d", *data+i*(*n)+j);
		}
	}
}

//6
//0 2 1 5 -1 -1
//2 0 2 3 -1 -1
//1 2 0 3 1 -1
//5 3 3 0 1 5
//-1 -1 1 1 0 2
//-1 -1 -1 5 2 0

//6
//0 5 -1 -1 5 1
//5 0 5 -1 -1 5
//-1 5 0 1 1 -1
//-1 -1 1 0 -1 10
//5 -1 1 -1 0 1
//1 5 -1 10 1 0
void cal_min_path(int *data, int n, int **path, int **m){
	int *s, sk;
	int nk;
	int mintemp, min_node;
	
	s = (int*)malloc(sizeof(int)*n);
	*path = (int*)malloc(sizeof(int)*n);    //path记录结点相邻前驱结点
	*m = (int*)malloc(sizeof(int)*n);       //m记录结点v0经过集合s的一个结点到达vj的最小路径，m[j]表示从v0到vj路径上，经过或不经过集合s中结点的最小路径长度，所以当集合s加入新结点，只需要计算v0经过新节点vp到达vp相邻节点的路径长度，更新m即可。

	if(s==NULL||*path==NULL||*m==NULL)
		perror("malloc failed
");
	//initialization
	for(sk=0; sk<n; sk++){
		*(s+sk)=0;
		*(*path+sk)=0;
		if(*(data+sk)!=-1)
			*(*m+sk)=*(data+sk);  //m记录集合S中元素与周边结点最小路径长度。
		else
			*(*m+sk)=INT_MAX;
	}
	*s=1;

	for(nk=0; nk<n; nk++){
		for(sk=0, mintemp=INT_MAX; sk<n; sk++){
			if(!s[sk]&&(*(*m+sk)!=INT_MAX)&&(*(*m+sk)<mintemp)){
				min_node = sk;
				mintemp = *(*m+sk);
			}
		}
		s[min_node] = 1;

		//min_node加入集合S后，更新m（需要比较v0->v_min_node->vj，vj∉S）
		for(sk=0; sk<n; sk++){
			if(!s[sk]&&*(data+min_node*n+sk)!=-1&&(*(*m+sk)>mintemp+*(data+min_node*n+sk))){
				*(*m+sk) = *(*m+min_node)+*(data+min_node*n+sk);
				*(*path+sk) = min_node;
			}
		}
	}
}

void dis_minpath(int n, int *path, int i){
	if(*(path+i)==0){
		printf("v0");
		return;
	}
	else{
		dis_minpath(n, path, *(path+i));
	}
	printf("->v%d", *(path+i));
}

int main(void){
	int *data, n, k;
	int *path, *min_len;

	input_graph_array(&data, &n);
	cal_min_path(data, n, &path, &min_len);

	for(k=1; k<n; k++){
		dis_minpath(n, path, k);
		printf("->v%d
", k);
	}

	system("pause");
	return 0;
}

(2).佛洛伊德算法-Floyd

佛洛伊德算法并不是用于单独求出两个结点的最小路径，而是用于求任意两个不同节点间的最小路径。当然，也可以使用上面所介绍的迪杰斯特拉算法对任意结点进行计算，但Floyd算法在代码上要更简洁些。

佛洛伊德算法使用的是动态规划的方法，所以我们应该定义出辅助空间具体含义，将问题分为子问题，并努力寻求所求目标的递推公式。

①假设m(k)[i,j]表示结点vi到vj经过一系列结点vp，p=1,2,3,...,k，vp就是所谓的中间结点，m(k)[i,j]可描述为结点vi经过若干个序号不超过k的中间结点到达结点vj的最小路径；

②m(-1)[i,j]由于结点序号不可能为-1或更小，所以m(-1)[i,j]表示图中结点间的直接路经长度；

③m(k)[i,j]即结点vi经过若干个序号不超过k的中间结点到达结点vj的最小路径无非有两种情况：1)结点vi到达结点vj的最小路径上不含vk；2)结点vi结点vj的最小路径上包含vk。

若vi->vj的最小路径上不含结点vk，则m(k)[i,j]=m(k-1)[i,j]；若vi->vj的最小路径上含有结点vk，那么vi->vj=vi->vk->vj，其中vi->vk的路径上经过了若干个序号不超过k-1的中间结点，vk->vj的路径上也经过了若干个序号不超过k-1的中间结点。因此m(k)[i,j]=min{m(k-1)[i,j] or m(k-1)[i,k]+m(k-1)[k,j]}；

④我们最终需要求出任意结点vi,vj在经过若干个中间结点(vp,p=1,2,3,...,n,p≠i or j)，所以我们就是求解m(n)[i,j]的值。

//佛洛伊德算法-Floyd(动态规划)
//①m[i,j]_k表示vi到vj经过不大于序号k的节点的最小路径，即vi->...->vj，其中...表示vp，p=1,2,3,...,k；
//②m[i,j]_k=min{m[i,j]_(k-1), m[i,k]_(k-1)+m[k,j]_(k-1)}，即取vi->vp->vj(vp,p=1,2,3,...,k-1)与vi->vp1->vk->vp2->vj(vp1,vp2,p1=1,2,3,...,k-1;p2=1,2,3,...,k-1)之间的较小值；
//③m[i,j]_n即为目标所求。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void perror(char *str){
	printf("%s", str);
	system("pause");
	exit(0);
}

void input_graph_array(int **data, int *n){
	int i,j;

	scanf("%d", n);
	*data = (int*)malloc(sizeof(int)*(*n)*(*n));
	if(*data==NULL)
		perror("malloc failed
");
	
	for(i=0; i<*n; i++){
		for(j=0; j<*n; j++){
			if(j==0)
				scanf("%d", *data+i*(*n));
			else
				scanf(" %d", *data+i*(*n)+j);
		}
	}
}

//6
//0 6 1 5 -1 -1
//6 0 5 -1 3 -1
//1 5 0 5 6 4
//5 -1 5 0 -1 2
//-1 3 6 -1 0 6
//-1 -1 4 2 6 0
void cal_min_path(int *data, int n, int **path, int **m){
	int k,i,j;

	*path = (int*)malloc(sizeof(int)*n*n);
	*m = (int*)malloc(sizeof(int)*n*n);

	//initialization
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			*(*m+i*n+j)=(*(data+i*n+j)<=-1)?INT_MAX:*(data+i*n+j);
			*(*path+i*n+j)=-1;
		}
	}

	for(k=0; k<n; k++){
		for(i=0; i<n; i++){
			for(j=0; j<n; j++){
				if(*(*m+i*n+k)!=INT_MAX&&*(*m+k*n+j)!=INT_MAX&&*(*m+i*n+j)>*(*m+i*n+k)+*(*m+k*n+j)){
					*(*m+i*n+j) = *(*m+i*n+k)+*(*m+k*n+j);
					*(*path+i*n+j) = k;
					//当需要有path推出最短路径时，原理是vi->vj,path(i,j)经过结点vk，然后递归查询path(i,k)=k'，则可知vi->vk经过结点vk'，继续递归查询path(i,k')，直至遇到-1结束。
				}
			}
		}
	}
}

void dis_minpath(int n, int *path, int i, int j){
	if(*(path+i*n+j)==-1)
		return;
	dis_minpath(n, path, i, *(path+i*n+j));
	printf("->v%d", *(path+i*n+j));
	dis_minpath(n, path, *(path+i*n+j), j);
}

void show_path(int n, int *path, int i, int j){
	printf("v%d", i);
	dis_minpath(n, path, i, j);
	printf("->v%d
", j);
}

int main(void){
	int *data, n, k;
	int *path, *min_len;
	int i,j;

	input_graph_array(&data, &n);
	cal_min_path(data, n, &path, &min_len);

	for(i=0; i<n; i++)
		for(j=0; j<n; j++){
			if(i==j)
				printf("v%d
", i);
			else
				show_path(n, path, i, j);
		}

	system("pause");
	return 0;
}

这里使用递归输出任意结点间的最小路径，从path(i,j)=k可知，vi->...->vk->...->vj，然后可又path(i,k)=k'可知，vi->...->vk'->...->vk->...vj，以此类推进行输出。

不知道大家有没有这个疑惑？因为m(k)[i,j]与m(k-1)[i,k]，m(k-1)[k,j]有关，那么在嵌套中直接修改m这个辅助数组不会对后面的计算产生影响？

我们假设前面计算了m(k)[i,j]=min{m(k-1)[i,k]+m(k-1)[k,j] or m(k-1)[i,j]}，

当我们需要计算m(k)[i',j']=min{m(k-1)[i',k]+m(k-1)[k,j'] or m(k-1)[i',j']}时，假设m(k-1)[i',k]在之前被m(k)[i,k]或m(k)[k,j]所覆盖，那么由m(k)[i',k]=min{m(k-1)[i',k]+m(k-1)[k,k] or m(k-1)[i',k]}，由于m(x)[k,k]=0，所以此时m(k)[i',k]=m(k-1)[i',k]；m(k)[k,j]证明类似。