中小型网站建设方案,温州专业微网站制作公司哪家好,wordpress外网访问网页异常,wordpress网站下载文件1.Floyd_Warshall算法
核心思路#xff1a;d[i][j] min{d[i][j], d[i][k] d[k][j]} 从i到j有两种路径#xff0c;经过k点或是不经过k点#xff0c;所以我们枚举k即可求所有路的最短路。 适用范围#xff1a;求任意两点间的最短路#xff0c;可以有负权#xff0c;可以…1.Floyd_Warshall算法
核心思路d[i][j] min{d[i][j], d[i][k] d[k][j]} 从i到j有两种路径经过k点或是不经过k点所以我们枚举k即可求所有路的最短路。 适用范围求任意两点间的最短路可以有负权可以是有向图可以是无向图但是n必须在200以内
#include iostream
#include stdio.h
#include string
#include string.h
#include queue
#include vector
#define INF 0x3f3f3f3fusing namespace std;int main()
{int n, m, s, t;while(~scanf(%d%d, n, m)){vectorvectorint dis(n);//vector二维可变长数组for(int i 0; i n; i){dis[i].resize(n, INF);//初始化设置dis[i]的长度并用INF作为初始值dis[i][i] 0;}for(int i 0; i m; i)//输入边a,b两点的权值是x{int a, b, x;scanf(%d%d%d, a, b, x);if(dis[a][b] x)dis[a][b] dis[b][a] x;}scanf(%d%d, s, t);for(int k 0; k n; k)for(int i 0; i n; i)for(int j 0; j n; j){if(dis[i][k] INF dis[k][j] INF)dis[i][j] min(dis[i][j], dis[i][k] dis[k][j]);}if(dis[s][t] ! INF)//可以求任意两点间最短路printf(%d\n, dis[s][t]);elseprintf(-1\n);}return 0;
}
2.Dijkstra算法
核心思路: D(s, t) {Vs … Vi … Vj … Vt}表示s到t的最短路其中i和j是这条路径上的两个中间结点那么D(i, j)必定是i到j的最短路如果存在这样一条最短路D(s, t) {Vs … Vi Vt}其中i和t是最短路上相邻的点那么D(s, i) {Vs … Vi} 必定是s到i的最短路。Dijkstra算法就是基于这样一个性质通过最短路径长度递增逐渐生成最短路。 适用情况 正权图上的单元最短路有向图无向图从单个源点出发到所有结点的最短路
设起始点为s
清除所有点的标记
设dis[s] 0,其他dis[i] INF
循环n次
{ 在所有未标记的节点中选出dis值最小的节点X给节点X标记对于从X出发可以到达的点y更新dis[y] min{dis[y], dis[x]w(x,y)}
}邻接矩阵实现
void dijkstra(int s)//s是起点
{memset(dis, INF, sizeof(dis));memset(vis,0,sizeof(vis);vis[s] 1;dis[s] 0;for(int i 1; i n; i)//执行n-1轮{int min_dis INF;int x;for(int j 1; j n; j)//寻找所有集合外的点到集合距离最小的点x{if(!vis[j] min_dis dis[j]){x j;min_dis dis[j];}}vis[x] 1;//然后把X加入到最短路点集中for(int j 1; j n; j)//更新集合外点到集合的距离{if(!vis[j])dis[j] min(dis[j], dis[x] mapp[x][j]);//x到j的距离dis[x]}}
}优先队列优化版
#include iostream
#include stdio.h
#include string
#include string.h
#include queue
#include vector
#define INF 0x3f3f3f3fusing namespace std;
const int maxn 105;
int dis[maxn], pre[maxn];struct Edge//边
{int u, v, w;Edge() {};Edge(int uu, int vv, int ww): u(uu), v(vv), w(ww) {};
};vectorEdge edges;//边数组
vectorint G[maxn];//存储每个节点对应的边的序号 void init(int nn)//清理
{for(int i 0; i nn; i)G[i].clear();edges.clear();
}void AddEdge(int uu, int vv, int ww)//加边
{edges.push_back(Edge(uu, vv, ww));int edgenum edges.size();G[uu].push_back(edgenum - 1);
}struct node//优先队列优化dis小的先出队
{int u, d;node() {};node(int uu, int dd): u(uu), d(dd) {};friend bool operator (node a, node b){return a.d b.d;}
};void dijkstra(int s)
{priority_queuenode q;memset(dis, INF, sizeof(dis));//dis初始化为INF dis[s] 0;q.push(node(s, dis[s]));while(!q.empty()){node cur q.top();q.pop();int from cur.u;if(cur.d ! dis[from])//减少了vis数组表示该节点被取出来过 continue;for(int i 0; i G[from].size(); i)//更新所有集合外点到集合的dis {Edge e edges[G[from][i]];if(dis[e.v] dis[e.u] e.w){dis[e.v] dis[e.u] e.w;pre[e.v] from;//存储父节点 q.push(node(e.v, dis[e.v]));//将有更新的dis加入到队列中 }}}
}
int main()
{int n, m;while(~scanf(%d%d, n, m) n m){init(n);for(int i 0; i m; i){int u, v, w;scanf(%d%d%d, u, v, w);AddEdge(u, v, w);AddEdge(v, u, w);}dijkstra(1);printf(%d\n, dis[n]);}return 0;
}3.SPFA算法
核心思路
设立一个先进先出的队列用来保存待优化的结点优化时每次取出队首结点u并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作如果v点的最短路径估计值有所调整且v点不在当前的队列中就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作直至队列空为止 适用情况可以正权可以有负权有向图无向图从单个源点出发到所有结点的最短路
代码参考 https://blog.csdn.net/Since_natural_ran/article/details/52955460
#includeiostream
#includecstdio
#includecstring
#includequeue
#includevector#define inf 0x3f3f3f3fusing namespace std;int dis[105],visit[105];
int n,m;class Node
{
public:int e,v;Node(int a,int b){e a,v b;}
};vectorNodes[105];void spfa()
{memset(dis,inf,sizeof(dis));memset(visit,0,sizeof(visit));dis[1] 0;queueintq;q.push(1);visit[1] true;while(!q.empty()){int u q.front();q.pop();visit[u] false;int num s[u].size();for(int i 0;i num; i){if(dis[u] s[u][i].v dis[s[u][i].e])continue;dis[s[u][i].e] dis[u] s[u][i].v;if(!visit[s[u][i].e]){q.push(s[u][i].e);visit[s[u][i].e] true;}}}
}int main()
{// freopen(in.txt,r,stdin);while(cinnm){if(n 0 m 0)break;for(int i 1;i n; i)s[i].clear();int a,b,c;for(int i 1;i m; i){cinabc;s[a].push_back(Node(b,c));s[b].push_back(Node(a,c));//这里无向}spfa();coutdis[n]endl;}return 0;
}
