这几天一直在看图论的东西，什么Dijkstra,Floyd，Prim,Kruskal等等的东西吧，之前总感觉这些东西好难，也就没怎么看，这段时间接触多了，每天都看那么一丢丢，感觉真的也就那么回事，什么东西都是要一点一点去学，慢慢的去掌握的不是么，所以看了好几天的东西，今天想花点时间去总结一次，就当做省赛前的小放松了，哈哈，其实平常也挺放松的.......好了，进入正题吧！
Dijkstra算法
Dijkstra算法是典型的 单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是 以起点为中心向外层扩展，直到扩展到终点为止。特别注意的是 Dijkstra算法要求图中不存在负权边。
Dijkstra单源最短路 邻接矩阵形式
/* * 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2) * 求出源beg到所有点的最短路径，传入图的顶点数和邻接矩阵cost[][] * 返回各点的最短路径lowcost[]，路径pre[]，pre[i]记录beg到i路径上的父节点，pre[beg] = -1 * 可更改路径权类型，但是权值必须为非负，下标0~n-1 */ const int MAXN = 1010; const int INF = 0x3f3f3f3f; // 表示无穷 bool vis[MAXN]; int pre[MAXN]; void Dijkstra(int cost[][MAXN], int lowcost[], int n, int beg) { for (int i = 0; i < n; i++) { lowcost[i] = INF; vis[i] = false; pre[i] = -1; } lowcost[beg] = 0; for (int j = 0; j < n; j++) { int k = -1; int min = INF; for (int i = 0; i < n; i++) { if (!vis[i] && lowcost[i] < min) { min = lowcost[i]; k = i; } } if (k == -1) { break; } vis[k] = true; for (int i = 0; i < n; i++) { if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]) { lowcost[i] = lowcost[k] + cost[k][i]; pre[i] = k; } } } }Dijkstra 单源最短路 邻接矩阵形式 双路径信息 /* *单源最短路径，dijkstra算法，邻接矩阵形式，复杂度为o(n^2) *两点间距离存入map[][]，两点间花费存入cost[][] *求出源st到所有点的最短路径及其对应最小花费 *返回各点的最短路径lowdis[]以及对应的最小花费lowval[] *可更改路径权类型，但是权值必须为非负，下标1~n */ const int MAXN=1010; const int INF=0x3f3f3f3f; int n,m; int lowdis[MAXN]; int lowval[MAXN]; int visit[MAXN]; int map[MAXN][MAXN]; int cost[MAXN][MAXN]; void dijkstra(int st) { int temp=0; for(int i=1;i<=n;i++) { lowdis[i]=map[st][i]; lowval[i]=cost[st][i]; } memset(visit,0,sizeof(visit)); visit[st]=1; for(int i=1;i<n;i++) { int MIN=INF; for(int j=1;j<=n;j++) { if(!visit[j]&&lowdis[j]<MIN) { temp=j; MIN=lowdis[j]; } } visit[temp]=1; for(int j=1;j<=n;j++) { if(!visit[j]&&map[temp][j]<INF) { if(lowdis[j]>lowdis[temp]+map[temp][j]) { lowdis[j]=lowdis[temp]+map[temp][j]; lowval[j]=lowval[temp]+cost[temp][j]; } else if(lowdis[j]==lowdis[temp]+map[temp[j]) { if(lowval[j]>lowval[temp]+cost[temp][j]) { lowval[j]=lowval[temp]+cost[temp][j]; } } } } } return; }Dijkstra起点Strat结点有权值
#define M 505 const int inf=0x3f3f3f3f; int num[M]; //结点权值 int map[M][M]; //图的临近矩阵 int vis[M]; //结点是否处理过 int ans[M]; //最短路径结点权值和 int dis[M]; //各点最短路径花费 int n,m,Start,End; //n结点数，m边数，Start起点,End 终点 void Dij(int v) { ans[v]=num[v]; memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { if(map[v][i]<inf) { ans[i]=ans[v]+num[i]; } dis[i]=map[v][i]; } dis[v]=0; vis[v]=1; for(int i=1;i<n;i++) { int u=0,min=inf; for(int j=0;j<n;j++) { if(!vis[j]&&dis[j]<min) { min=dis[j]; u=j; } } vis[u]=1; for(int k=0;k<n;k++) { if(!vis[k]&&dis[k]>map[u][k]+dis[u]) { dis[k]=map[u][k]+dis[u]; ans[k]=ans[u]+num[k]; } } for(int k=0;k<n;k++) { if(dis[k]==map[u][k]+dis[u]) { ans[k]=max(ans[k],ans[u]+num[k]); } } } printf("%d %d\n",dis[End],ans[End]);//输出终点最短路径花费、最短路径结点权值和 } int main() { scanf("%d%d%d%d",&n,&m,&Strat,&End); for(int i=0;i<n;i++) scanf("%d",&num[i]); memset(vis,0,sizeof(vis)); memset(map,0x3f,sizeof(map)); for(int i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(map[x][y]>z) { map[x][y]=z; map[y][x]=z; } } Dij(Start); return 0; }Floyd算法
Floyd-Warshallsu算法是解决任意两点间的最短路径的一种算法，可以处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
算法描述：
a)从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有相连，则权为无穷大。
b)对于每一对定点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短.如果是，那么就更新它.
Floyd算法 邻接矩阵形式
/* *Floyd算法，求从任意节点i到任意节点j的最短路径 *cost[][]：初始化为INF(cost[i][i]:初始化为0) *lowcost[][]:最短路径，path[][]:最短路径(无限制) */ const int MAXN=100; int cost[MAXN][MAXN]; int lowcost[MAXN][MAXN]; itn path[MAXN][MAXN]; void Floyd(int n) { memcpy(lowcost,cost,sizeof(cost)); memset(path,-1,sizeof(path)); for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(lowcost[i][j]>(lowcost[i][k]+lowcost[k][j])) { lowcost[i][j]=lowcost[i][k]+lowcost[k][j]; path[i][j]=k; } } } Floyd算法 点权 + 路径限制 /*Floyd算法，求任意节点i到任意节点j的最短路径 *cost[][]:初始化为INF(cost[i][i]:初始化为0) *val[]:点权，lowcost[][]:除起点，终点外的点权之和+最短路径 *path[][]：路径限制，要求字典序最小的路径，下表1~N */ const int MAXN=110; const int INF=0x3f3f3f3f; int val[MAXN]; //点权 int cost[MAXN][MAXN]; int lowcost[MAXN][MAXN]; int path[MAXN][MAXN]; //i~j路径中第一个结点 void Floyd(int n) { memccpy(lowcost,cost,sizeof(cost)); for(itn i=0;i<=n;i++) { for(int j=0;j<=n;j++) { path[i][j]=j; } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int temp=lowcost[i][k]+lowcost[k][j]+val[k]; if(lowcost[i][j]>temp) { lowcost[i][j]=temp; path[i][j]=path[i][k]; } else if(lowcost[i][j]==temp&&path[i][j]>path[i][k]) path[i][j]=path[i][k]; } return; } Prim算法 prim算法：每次选取一条边，该边满足：1.一端已选，一端未选；2.该边权值最小。算法描述：Prim只与定点有关，求最小生成树的时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树
/* * Prim求MST * 耗费矩阵cost[][]，初始化为INF，标号从0开始，0 ~ n－1 * 返回最小生成树的权值，返回-1表示原图不连通 */ const int INF = 0x3f3f3f3f; const int MAXN = 110; bool vis[MAXN]; int lowc[MAXN]; int cost[MAXN][MAXN]; // 修正cost（添加边） void updata(int x, int y, int v) { cost[x - 1][y - 1] = v; cost[y - 1][x - 1] = v; return ; } int Prim(int cost[][MAXN], int n) // 0 ~ n - 1 { int ans = 0; memset(vis, false, sizeof(vis)); vis[0] = true; for (int i = 1; i < n; i++) { lowc[i] = cost[0][i]; } for (int i = 1; i < n; i++) { int minc = INF; int p = -1; for (int j = 0; j < n; j++) { if (!vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } if (minc == INF) { return -1; // 原图不连通 } ans += minc; vis[p] = true; for (int j = 0; j < n; j++) { if (!vis[j] && lowc[j] > cost[p][j]) { lowc[j] = cost[p][j]; } } } return ans; } Kruskal算法 在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。克鲁斯卡尔算法的执行步骤： 第一步：在带权连通图中，将边的权值排序； 第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。 第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。
/* * Kruskal算法求MST * 对边操作，并排序 * 切记：初始化赋值问题（tol） */ const int MAXN = 110; // 最大点数 const int MAXM = 10000; // 最大边数 int F[MAXN]; // 并查集使用 struct Edge { int u; // 起点 int v; // 终点 int w; // 权值 } edge[MAXM]; // 存储边的信息 int tol; // 边数，加边前赋值为0 void addEdge(int u, int v, int w) { edge[tol].u = u; edge[tol].v = v; edge[tol++].w = w; return ; } bool cmp(Edge a, Edge b) { // 排序函数，将边按照权值从小到大排序 return a.w < b.w; } int find(int x) { if (F[x] == x) { return x; } else { return F[x] = find(F[x]); } } int Kruskal(int n) // 传入点数，返回最小生成树的权值，如果不连通则返回-1 { for (int i = 0; i <= n; i++) { F[i] = i; } sort(edge, edge + tol, cmp); int cnt = 0; // 计算加入的边数 int ans = 0; for (int i = 0; i < tol; i++) { int u = edge[i].u; int v = edge[i].v; int w = edge[i].w; int tOne = find(u); int tTwo = find(v); if (tOne != tTwo) { ans += w; F[tOne] = tTwo; cnt++; } if (cnt == n - 1) { break; } } if (cnt < n - 1) { return -1; // 不连通 } else { return ans; } }
