屏幕快照 2018-04-26 下午4.11.23.png
/*
Floyd-Warshall 算法：
允许在顶点k中转，可以通过e[a][b] > e[a][k] + e[k][b], 来找到顶点a和顶点b的最短路程，如果顶点k
是从1 — n,那么就找到顶点a到顶点b允许在顶点1—n中转的最短距离。
当将一个顶点k作为中转点，进行完一轮边的松弛操作(e[i][j] > e[i][k] + e[k][j] 则e[i][j] = e[i][k] + e[k][j])后，就会消除顶点k对最短距离的影响~当k从1—n,就相当于逐步消除了顶点1—n对最短距离的 影响，那么此时的结果就是最短距离~
*/
#pragma mark - - Floyd-Warshall 算法
-(void)test1 {
// 存储边
int k[9][3] = {{0,0,0},{1,2,2},{1,3,6},{1,4,4},{2,3,3},{3,1,7},{3,4,1},{4,1,5},{4,3,12}};
int n =4; //顶点数
int m =8; //边数
int inf = 9999; // 表示无穷大∞
// e[i][j] 表示i到j的距离为e[i][j]
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j] = 0;
}else {
e[i][j] = inf;
}
}
}
// 赋值
for (int i=1; i<=m; i++) {
int u = k[i][0];
int v = k[i][1];
e[u][v] =k[i][2];
}
// Floyd-Warshall 算法核心
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (e[i][j] > e[i][k] + e[k][j]) {
e[i][j] = e[i][k] + e[k][j];
}
}
}
}
// 打印 数据
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
printf("%4d",e[i][j]);
}
printf("\n");
}
printf("\n");
}
/*
Dijkstra 算法：每次找到离源点最近的点，然后以该点为中心扩展，最终得到源点到其余所有点的最短距离
当找到一个离源点最近的顶点v时，dis[v]的值就确定了，因为不可能存在一个顶点k使得dis[v]>dis[k]+e[k][v]
(e[k][v]>0);然后以顶点v为中转点，对边进行松弛操作，即消除了顶点v对最短距离的影响。然后再从其余点中，再
找到一个离源点最近的点，重复上述操作
*/
#pragma mark - - Dijkstra 算法
-(void)test2 {
// 存储边
int k[9][3] = {{0,0,0},{1,2,2},{1,3,6},{1,4,4},{2,3,3},{3,1,7},{3,4,1},{4,1,5},{4,3,12}};
int inf=9999;
int n=4; // 顶点数
int m=8; // 边数
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else {
e[i][j]=inf;
}
}
}
// 赋值
for (int i=1; i<=m; i++) {
int u = k[i][0];
int v = k[i][1];
e[u][v] =k[i][2];
}
// dis[] 存储离源点的最短路程
int dis[10];
for (int i=0; i<10; i++) {
dis[i] =inf;
}
// book[] 标记离源点最近的点
int book[10] ={0};
// 设置源点
dis[1] =0;
for (int i=1; i<=n; i++) {
int min =inf;
int u=1; //记录离源点最近的点
// 找离源点最近的顶点
for (int i=1; i<=n; i++) {
if (dis[i]<min && book[i]==0) {
min =dis[I];
u=I;
}
}
// 标记顶点u
book[u]=1;
// 允许在顶点u中转，扩展其他点到源点的距离
for (int v=1; v<=n; v++) {
if (dis[v]>dis[u]+e[u][v]) {
dis[v] = dis[u]+e[u][v];
}
}
}
// 打印 数据
for (int i=1; i<=n; i++) {
printf("%4d",dis[I]);
}
printf("\n");
}
/*
Bemall-Ford 算法:对所有边进行松弛操作，每进行一轮，就相当于扩充了一些新边。当进行了k轮时，相当于
找到了从源点出发“最多经过k条边”到达其余各个顶点的最短距离～最短路径上最多有n-1条边。故需要进行n-1轮
如果进行n-1轮，还可以继续对边松弛成功，那必定存在负权回路
*/
#pragma mark - - Bellman-Ford 算法
-(void)test3 {
int k[9][3] = {{0,0,0},{1,2,2},{1,3,6},{1,4,4},{2,3,3},{3,1,7},{3,4,1},{4,1,5},{4,3,12}};
int inf =9999; // 表示无穷大
int n=4; // 顶点数
int m=8; // 边数
// u[i] v[i] 分别表示编号为i的边的顶点
// v[i] 表示编号为i的边的权值
int u[10];
int v[10];
int w[10];
for (int i=1; i<=m; i++) {
u[i] = k[i][0];
v[i] = k[i][1];
w[i] = k[i][2];
}
//dis[i] 表示顶点i到源点的最短距离
int dis[10];
for (int i=0; i<10; i++) {
dis[i] =inf;
}
// 设置源点1
dis[1] =0 ;
// 核心代码
for (int i=1; i<=n-1; i++) {
int check=0;
for (int j=1; j<=m; j++) {
if (dis[v[j]] > dis[u[j]] + w[j]) {
dis[v[j]] = dis[u[j]] + w[j];
check =1;
}
}
/*
check=0 表示当前这轮对边的松弛操作 不能使dis[]发生变化,相等于没有扩充新的边，
那么即使再次循环，也不会松弛成功。故可以提前退出循环
*/
if (check==0) {
break ;
}
}
// 检查 是否有负权回路
int flag=0;
for (int i=1; i<=m; i++) {
if (dis[v[i]] > dis[u[i]] + w[i]) {
flag =1;
}
}
if (flag==1) {
printf("存在负权回路 \n");
}else {
// 打印 数据
for (int i=1; i<=n; i++) {
printf("%4d",dis[I]);
}
printf("\n");
}
}
/*
Bellman-Ford 的队列优化： 每次仅对最短路程发生变化的顶点的所有出边执行松弛操作
当一个顶点k的dis[u[i]]的值确定了，那么由这个顶点直接扩充的dis[v[i]] = dis[u[i]] + w[i],也不会
发生变化，故只需对最短路程发生变化的顶点的所有出边执行松弛操作
对一个顶点的所有出边进行松弛操作，如果存在dis[v[i]] > dis[u[i]] +w[i],则将v[i]点加入队列，
继续上述操作(head++)
Bellman-Ford 算法，我们可以知道 最多执行n*m次松弛操作，就可以获得所有点到源点的最短回路。
*/
#pragma mark - - Bellman-Ford 的 队列优化
-(void)test4 {
int k[9][3] = {{0,0,0},{1,2,2},{1,3,6},{1,4,4},{2,3,3},{3,1,7},{3,4,1},{4,1,5},{4,3,12}};
int inf =9999; // 表示无穷大
int n=4; // 顶点数
int m=8; // 边数
// u[i] v[i] 分别表示编号为i的边的顶点
// v[i] 表示编号为i的边的权值
int u[10];
int v[10];
int w[10];
// first[i] 表示顶点i的第一条边的编号
int first[10];
for (int i=0; i<10; i++) {
first[i] = -1;
}
// next[i] 表示边i的下一条边的编号
int next[10];
for (int i=1; i<=m; i++) {
u[i] = k[i][0];
v[i] = k[i][1];
w[i] = k[i][2];
next[i] = first[u[I]];
first[u[i]] =I;
}
//dis[i] 表示顶点i到源点的最短距离
int dis[10];
for (int i=0; i<10; i++) {
dis[i] =inf;
}
// 初始化队列
int que[100];
int head =1;
int tail =1;
// book[]
int book[10] = {0};
// 设置源点1
dis[1] =0 ;
que[tail] =1;
tail ++;
book[1] =1;
// 记录松弛操作的次数
int sum=0;
// 标示是否有负权回路
int flag=0;
while (head < tail) {
// 当前顶点
int t = que[head];
// 获取顶点k的第一条边
int k = first[t];
while (k!=-1) {
sum ++;
if (dis[v[k]] > dis[u[k]] + w[k]) {
dis[v[k]] = dis[u[k]] + w[k];
if (book[v[k]] == 0) {
book[v[k]] =1;
que[tail] = v[k];
tail ++;
}
}
// 下一条边
k=next[k];
}
// 出队
/*
当一个顶点的最短路程变短后，需要对这个顶点的所有边进行松弛操作，但是如果这个顶点的最短路程
再次变小，需要再次对这个顶点的所有边进行松弛操作～
*/
book[que[head]] = 0; //把出队的点重新标记为0
head ++ ; // head++ 才能继续执行队列里的其他点
// 当图不存在负权回路时，最多会进行n*m次松弛操作
// 如果sum(松弛操作次数)>n*m+1 ，那一定存在负权回路
// 为什么是n*m,Bellman-Ford 算法最多执行(n-1)*m次就可以使源点到各个顶点的距离达到最小值
if (sum>n*m+1) {
flag =1;
break ;
}
}
if (flag==1) {
printf("存在负权回路 \n");
}else {
// 打印 数据
for (int i=1; i<=n; i++) {
printf("%4d",dis[I]);
}
printf("\n");
}
}
图片来源于啊哈！算法.png
