中文单页面网站模板,深圳公共交易资源平台,信息型网站有哪些,天津推广的平台关注#xff1a;算法思路#xff0c;时间复杂度#xff0c;适用情况#xff08;单源/多源#xff0c;负边权/负边权回路#xff09;
复习弗雷德算法--基于动态规划--多源--负边权--时间复杂度O(v^3) int的最大值是0x7fffffff
#include iostream
using namesp…
关注算法思路时间复杂度适用情况单源/多源负边权/负边权回路
复习弗雷德算法--基于动态规划--多源--负边权--时间复杂度O(v^3) int的最大值是0x7fffffff
#include iostream
using namespace std;
#define inf 100000
int n, m;
int a[105][105];
int dp[105][105];
int main() {cin n m;for (int i 1; i n; i) {for (int j 1; j n; j) {a[i][j] inf;if (i j) {a[i][j] 0;}}}int x, y, w;for (int i 1; i m; i) {cin x y w;a[x][y] w;}//初始化dpfor (int i 1; i n; i) {for (int j 1; j n; j) {dp[i][j] a[i][j];}}for (int k 1; k n; k) {//枚举中转点for (int i 1; i n; i) {for (int j 1; j n; j) {dp[i][j] min(dp[i][j], dp[k - 1][i] dp[k][j]);//不能交换循环位置无法解释了}}}for (int i 1; i n; i) {for (int j 1; j n; j) {cout dp[i][j] ;}cout endl;}return 0;
}复习迪斯拉算法--基于贪心--单源--不能处理负边权--时间复杂度O(v^3)
#includeiostream
using namespace std;
#define INF 65535
int g[105][105];
int dist[105], path[105];
int flag[105];//1 i的最短路径已经确定
int n, m;
void Dijkstra(int s) {//起点到起点flag[s] 1;dist[s] 0;path[s] s;int minn INF;int t;for (int i 1; i n; i) {//循环n-1次minn INF;for (int j 0; j n; j) {if (flag[j] 0 dist[j] minn) {minn dist[j];t j;//t点是dist最小的点}}flag[t] 1;//确定最小路径for (int j 0; j n; j) {if (flag[j] 0 dist[j] (dist[t] g[t][j])) {dist[j] dist[t] g[t][j];path[j] t;}}}}
int main() {int s;//起点cin n m;for (int i 0; i n; i) {for (int j 0; j n; j) {if (i j)g[i][j] 0;else g[i][j] INF;}}int x, y, w;for (int i 1; i m; i) {cin x y w;g[x][y] g[y][x] w;}cin s;dist[s] 0;for (int i 0; i n; i) {dist[i] g[s][i];if (g[s][i] INF) {path[i] -1;}else {path[i] s;}}Dijkstra(s);for (int i 0; i n; i) {cout s到 i 的最短路径长度是 dist[i] :;//倒叙输出路径cout i ;int j i;while (path[j] ! j) {cout path[j] ;j path[j];}cout endl;}return 0;
}
//9 16
//0 1 1
//0 2 5
//1 2 3
//1 3 7
//1 4 5
//2 4 1
//2 5 7
//3 4 2
//3 6 3
//4 5 3
//4 6 6
//4 7 9
//5 7 5
//6 7 2
//6 8 7
//7 8 4
//0 优化无序找最小(通过小顶堆)--邻接表存图--链式前向星--priority_quque从n到logn
#includeiostream
#includequeue
#includevector
using namespace std;
typedef pairint, int PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queuePII, vectorPII, greaterPIIq;
void add(int x,int y,int w) {cut;//从1开始e[cut].to y;e[cut].w w;e[cut].next head[x];head[x] cut;cut;
}void dijkstra() {memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] 0;q.push({ 0,s });while (q.size()) {PII t q.top();q.pop();int u t.second, d t.first;if (flag[u] 1)continue;flag[u] 1;for (int i head[u]; i ! -1; i e[i].next) {//i即u的出边int v e[i].to;//u的邻接点if (flag[v] 0 dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;q.push({ dis[v],v });}}}
}
int main() {scanf(%d %d %d, n, m, s);int x, y, w;memset(head, -1, sizeof(head));for (int i 1; i m; i) {scanf(%d %d %d, x, y, w);add(x, y, w);}dijkstra();for (int i 1; i n; i) {printf(%d , dis[i]);}return 0;
}
//4 5 1
//1 2 1
//1 4 1
//2 3 2
//4 3 2
//1 3 6
弗雷德和迪斯拉算法共性 福特算法Bellman-Ford算法--暴力遍历无脑松弛--单源--时间复杂度O(ve)--能处理负边权--不能处理负权回路但是能判断是否有负权回路让他循环到n次 #includeiostream
#includevector
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {int a, b, w;
}e[10005];
void ford() {int x, y, w;bool flag 0;for (int i 1; i n - 1; i) {flag 0;for (int j 0; j m; j) {x e[j].a;y e[j].b;w e[j].w;if (dis[x] w dis[y]) {dis[y] dis[x] w;flag 1;}}if (flag 0)break;//没有松弛操作说明全部已经松弛了}
}int main() {scanf(%d %d, n, m);for (int i 0; i m; i) {scanf(%d %d %d, e[i].a, e[i].b, e[i].w);}scanf(%d, s);memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] 0;ford();for (int i 1; i n; i) {printf(%d , dis[i]);}return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1
下面改一点点能判断有负权回路负环
#includeiostream
#includevector
using namespace std;
int n, m;
int dis[105];
int s;//起点
struct Edge {int a, b, w;
}e[10005];
void ford() {int x, y, w;bool flag 0;for (int i 1; i n; i) {//执行第n次flag 0;for (int j 0; j m; j) {x e[j].a;y e[j].b;w e[j].w;if (dis[x] w dis[y]) {//第n次不执行松弛操作dis[y] dis[x] w;flag 1;}}//if (flag 0)break;//没有松弛操作说明全部已经松弛了}if (flag 1)printf(有负权回路);else printf(没有负权回路);
}int main() {scanf(%d %d, n, m);for (int i 0; i m; i) {scanf(%d %d %d, e[i].a, e[i].b, e[i].w);}scanf(%d, s);memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] 0;ford();for (int i 1; i n; i) {printf(%d , dis[i]);}return 0;
}
//5 5
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3
//1
缺点枚举顺序导致时间长一点,可以优化优化后就是SPFA算法。
SPFA算法能判断负环--时间复杂度难以计算 #includeiostream
#includequeue
#includevector
using namespace std;
typedef pairint, int PII;
int n, m, cut;
int flag[105];
int dis[105];
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queuePII, vectorPII, greaterPIIq;
void add(int x,int y,int w) {cut;//从1开始e[cut].to y;e[cut].w w;e[cut].next head[x];head[x] cut;cut;
}
void SPFA() {queueintq;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] 0;flag[s] 1;//标记s有没有被入队q.push(s);while (!q.empty()) {int u q.front();q.pop();flag[u] 0;for (int i head[u]; i ! -1; i e[i].next) {int v e[i].to;//v是u的邻接点if (flag[v] 0 dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;q.push(v);flag[v] 1;}}}
}
int main() {scanf(%d %d %d, n, m, s);int x, y, w;memset(head, -1, sizeof(head));for (int i 1; i m; i) {scanf(%d %d %d, x, y, w);add(x, y, w);}SPFA();for (int i 1; i n; i) {printf(%d , dis[i]);}return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3判负环加上use以下代码只比上一个代码多use但是已经注释
#includeiostream
#includequeue
#includevector
using namespace std;
typedef pairint, int PII;
int n, m, cut;
int flag[105];
int dis[105];
//int use[105];//用于判断负环
int s;//起点
struct Edge {int to, next, w;
}e[10005];
int head[105];
priority_queuePII, vectorPII, greaterPIIq;
void add(int x,int y,int w) {cut;//从1开始e[cut].to y;e[cut].w w;e[cut].next head[x];head[x] cut;cut;
}
void SPFA() {queueintq;memset(dis, 0x3f3f3f3f, sizeof(dis));dis[s] 0;flag[s] 1;//标记s有没有被入队//use[s];q.push(s);while (!q.empty()) {int u q.front();q.pop();flag[u] 0;for (int i head[u]; i ! -1; i e[i].next) {int v e[i].to;//v是u的邻接点if (flag[v] 0 dis[v] dis[u] e[i].w) {dis[v] dis[u] e[i].w;q.push(v);//use[v];flag[v] 1;//if(use[v]n)}}}
}
int main() {scanf(%d %d %d, n, m, s);int x, y, w;memset(head, -1, sizeof(head));for (int i 1; i m; i) {scanf(%d %d %d, x, y, w);add(x, y, w);}SPFA();for (int i 1; i n; i) {printf(%d , dis[i]);}return 0;
}
//5 5 1
//2 3 2
//1 2 - 3
//1 5 5
//4 5 2
//3 4 3时间复杂度吃瓜
