印刷网站开发的可行性报告/谷歌官网下载app

//Floyed-Warshall算法 O(N^3)
/*
经典的多源最短路径算法
作用：1.求最短路。 2.判断一张图中的两点是否相连。
思想：3层循环；第一层枚举中间点k，第二层与第三层枚举两个端点i，j。若有dis[i][j] > dis[i][k] + dis[k][j] 则把dis[i][j]更新成dis[i][k] + dis[k][j]一般我们会说这是一个动态规划算法.
因为它有递推公式:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
三重循环,k要写外面,里面的i,j是对称的,*/
//如何进行初始化:
//1.
void init(){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dis[i][j] = inf;if(i == j) dis[i][j] = 0;}}
}
//2.
void init(){for(int i=0;i<=n;i++){for(int j=i+1;j<=n;j++){dis[j][i] = dis[i][j] = inf;}dis[i][i]=0;}
}
//3.
memset(dis,0x3f,sizeof(dis));//Floyd实现：
void floyd(){//先进行初始化//实现for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];/*可以快那么一点点for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){if(i!=k){for(int j=1;j<=n;j++){if(i!=j &&j!=k){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);	}}}}}*/
}
//判断两点是否可以通过某条路径相连
void floydbool(){bool dis[100][100];//初始化 disfor(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = dis[i][j] ||(dis[i][k]&&dis[k][j]);	}}}}//路径还原//方法一：栈实现
int pre[N][N];//记录当前顶点的前一个顶点
void init(){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dis[i][j] = inf;if(i == j) dis[i][j] = 0;//对pre的初始化：这个地方要赋值成ipre[i][j] = i;}}
}
void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j]){dis[i][j]=dis[i][k]+dis[k][j];pre[i][j] = pre[k][j];//i->k->j 记录k->j}
}
void printpath()
{stack<int> path;int start = 1;int temp = pre[start][n];//起点到终点//读取终点的前一个节点的位置path.push(n);//加入终点while(true){path.push(temp);//第一次加入的是终点前一个节点的位置if(temp == start) break;//如果已经把起点加进去了之后就可以推出temp = pre[start][temp];//获取前一个节点}while(!path.empty()){//输出cout<<path.top()<<endl;path.pop();}
}
//非栈实现：
void init(){for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dis[i][j] = inf;if(i == j) dis[i][j] = 0;//对pre的初始化pre[i][j] = j;//这个赋值赋值成j}}
}
void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j]){dis[i][j]=dis[i][k]+dis[k][j];pre[i][j] = pre[i][k];//i->k->j 记录i->k }
}
void printpath2()
{int start = 1;int eend = n;cout<<start<<endl;;int temp = pre[start][eend];while(true){cout<<temp<<endl;if(temp == eend) break;temp = pre[temp][eend];
}/*
5 5
1 2 1
2 4 1
2 3 4
4 3 1
3 5 3
1
2
4
3
5
*/
//其他方式的路径还原：递归实现
//初始化
path[i][j] = 0;
//floyd
path[i][j] = k;
//path[i][j]表示从i  到  j 必须经过path[i][j];
void printpath3(int i,int j){if(i == j) return 0;printpath3(i,path[i][j]);cout<<path[i][i]<<endl;printpath3(path[i][j],j);}