数据存储：
个别波及最短门路的图都有大量数据须要存储解决，因而肯定要正当抉择存储构造，并可能正确初始化，只有这些筹备工作做好了，上面的算法才有进行上来的可能性。个别有邻接矩阵和邻接表两种模式来存储图的与边相干的信息。特地的，应用邻接表时要独自创立构造体来存储信息。而存储点权只能应用一维数组。此外，还要设置拜访标记数组，前驱数组，记录结点不同松弛变量对应值的数组，或有时开拓动静数组以记录门路。
const int maxv = 1010;
const int INF = 0x3fffffff;
struct edge{//此处为应用邻接表存储图的边权时结构的构造体
int v, dis, cost;
};
int n;
int weight[maxv]; //记录点权
int d[maxv], c[maxv], w[maxv]; //记录不同松弛变量对应结点的值
int pre[maxv]; //记录每个结点的前驱来复原门路
int num[maxv]; //SPFA判断负环时应用
int pathCot[maxv]; //用于统计最短门路的条数
bool vis[maxv], inq[maxv]; //别离为拜访标记和入队标记
int dis[maxv][maxv], cost[maxv][maxv]; //记录不同的边权
vector<int> temp, ans;
set<int> pre[maxv]; //此处供SPFA从新统计最短门路条数时应用Dijkstra算法：
Dijkstra解决的是单源最短路问题，且基于松弛变量的优化策略是针对达到同一结点存在不同最短门路时应用的，是达到同一结点不同门路的纵向比拟。但有时可能存在不同结点之间抉择最优门路，故还要在算法完结后进行横向比拟。
void dijkstra(int s){
//开拓的所有数组都要初始化
fill(d, d+maxv, INF);
fill(c, c+maxv, INF);
fill(w, w+maxv, 0);
fill(vis, vis+maxv, false);
//依据源结点初始化
d[s] = 0;
c[s] = 0;
w[s] = weight[s];
//进入算法
for(int i = 0; i < n; i++){//共进行n轮，一轮确定一个点
int u = -1, Min = INF;
for(int j = 1; j <= n; j++){//这个要依据具体结点编号状况来看，个别是1-n
if(!vis[j] && d[j] < Min){
u = j;
Min = d[j];
}
}
if(u == -1) break;
vis[u] = true;
for(edge x: G[u]){//此处给出了邻接表模式的简洁遍历形式
int v = x.v, dis = x.dis, cost = x.cost;
...
}
for(int v = 1; v <= n; v++){
if(!vis[v] && dis[u][v] != INF){
if(d[u] + dis[u][v] < d[v]){//上面有几个松弛变量就有几个断定，留神更新相应数组的值
}else if(...){
...
}else if(...){
...
}
}
}
}
}SPFA算法：
该算法次要用于判断负环，且模式看上去更简洁。个别非必要还是不倡议应用该算法，因为若须要统计最短门路条数时，该算法很麻烦，每次更新都要从新统计，具体做法如下所示。
bool SPFA(int s){
fill(d, d+maxv, INF);
fill(c, c+maxv, INF);
fill(w, w+maxv, 0);
fill(num, num+maxv, 0);
fill(pathCot, pathCot+maxv, 0);
fill(inq, inq+maxv, false);
d[s] = 0;
c[s] = 0;
w[s] = weight[s];
pathCot[s] = 1;
queue<int> q;
q.push(s);
inq[s] = true;
num[s]++;
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = false;
for(int v = 1; v <= n; v++){
if(dis[u][v] != INF){
if(d[u] + dis[u][v] < d[v]){//上面仅给出对最短门路条数的更新
...
pathCot[v] = pathCot[u];
pre[v].clear();
pre[v].insert(u);
...
}else if(...){
...
pathCot[v] = 0;
pre[v].insert(u);
for(auto it = pre[v].begin(); it != pre[v].end(); it++){//从新统计最短门路条数
pathCot[v] += pathCot[*it];
}
...
}else if(...){
...
}
if(...){//此处断定条件是后面是否更新过
if(!inq[v]){
q.push(v);
inq[v] = true;
num[v]++;
if(num[v] >= n) return false;
}
}
}
}
}
return true;
}DFS算法：
该办法应用范畴很广，简直能够解决所有图论相干问题，且搭配回溯剪枝应用成果更佳。然而此法比拟灵便，没有固定的模板来套，且有许多细节要去解决，故没有十足把握或非必须倡议还是应用Dijkstra算法，毕竟当做模板间接用。应用DFS时，回溯时复原相应变量的值很重要，要十分小心。个别DFS针对性较强，有确定的源点和起点。
void dfs(int now, int ...){//个别dfs的形参中能够退出相干的累加量，从而在回溯时不必复原
if(...) return; //回溯剪枝
if(...){//达到指定结点，进行断定
}
for(...){//寻找下一个符合条件的递归结点
//退出门路
temp.push_back(now);
//设置拜访
vis[i] = true;
//耗费相应的信息
...
//递归进入下一层
dfs(..., ...);
//复原相应的信息
...
//设为未拜访
vis[i] = false;
//从门路中弹出
temp.pop_back();
}
}
int main(){
...
temp.push_back(0);
vis[0] = true;
dfs(0, ...);
vis[0] = false;
temp.pop_back();
...
return 0;
}Floyd算法：
用来解决全源最短路问题，但因为是三次方的工夫复杂度，故个别要求结点数小于200，也因而适宜应用邻接矩阵。
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][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]){//更新两点间的最短门路
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
发表回复