网站建设基,高职高专图书馆网站建设,2345软件管家,最常用的网站开发工具全部代码
全部代码在github acwing 上 正在更新 https://github.com/stolendance/acwing 图论 欢迎大家star与fork
单源最短路问题 先用spfa算法 不行再换其他的
spfa-超级万能 说不定比dijsktra还快
dis[] 代表第k到某一点的最短距离
queue 代表刚被更新的点 它有可能更…全部代码
全部代码在github acwing 上 正在更新 https://github.com/stolendance/acwing 图论 欢迎大家star与fork
单源最短路问题 先用spfa算法 不行再换其他的
spfa-超级万能 说不定比dijsktra还快
dis[] 代表第k到某一点的最短距离
queue 代表刚被更新的点 它有可能更新其他路径 所以检查它的出边
isin代表该点是否在queue中
队列放入起点 -k
while(队列不为空)取出队头遍历所有t的出边 t-wb如果dis[b]dis[t]w[t,b],更新,如果b不在队列中,加入btypedef long long ll;
typedef pairll,ll pll;
struct Edge
{int next;int val;Edge(int next_,int val_):next(next_),val(val_){;}
};
class Solution {
public:int networkDelayTime(vectorvectorint times, int n, int k) {vectorvectorEdge graph(n1);for(auto item:times){int aitem[0];int bitem[1];int citem[2];graph[a].push_back(Edge(b,c));}vectorll dis(graph.size(),INT_MAX);vectorint isin(graph.size(),0);queueint ls;ls.push(k);dis[k]0;isin[k]1;while(ls.size()){int tls.front();ls.pop();isin[t]0;for(int i0;igraph[t].size();i){// k-t-idint distancegraph[t][i].val;int idgraph[t][i].next;if(dis[t]distancedis[id]){dis[id]dis[t]distance;if(isin[id]0){ls.push(id);isin[id]1;}}}}int rs *max_element(dis.begin()1,dis.end());if(rsINT_MAX) return -1;else return rs;}
};朴素版dijsktra -单源最短路-所有边权重都是正数 基于 稠密图(邻接矩阵)
s:当前已经确定最短路径距离的点 dis[0 ]0 dis[i]OO 只有起点被确定到了 for(i 1 …n) t《- 不在s中的距离最近的点 s〈-t 用t更新其他点的距离(看下) dij实现的时候是通过 将距离设置成无穷大 来表达 不可达 dij 由于边很多, 稠密图 所以用邻接矩阵存即可 dij 需要找n个点 所以外层是一个for循环x 总结下来:1. 把未加入的最近的加进来2. 标记加入3. 根据加入的点更新距离#includeiostream
#includevector
using namespace std;
#define INA INT_MAX
//https://leetcode.cn/problems/network-delay-time/
int networkDelayTime(vectorvectorint times, int N, int k) {// 因为点的坐标是从1开始 , 所以开N1个// 直接在graph上更新 方便很多// graph要采用long long INT_MAX某个数 不会变成负数vectorvectorlong long graph(N1,vectorlong long(N1,INT_MAX));for(int i1;iN;i) graph[i][i]0;for(auto e:times) graph[e[0]][e[1]]e[2];vectorint vis(graph.size(),0);vis[k]1;// 只要找下除了起点的接下来的点for(int i1;igraph.size()-1;i){int minid0,minxINA;// 在没有使用过的检查最短的距离for(int j1;jgraph.size();j){if(vis[j]0graph[k][j]minx){minidj;minxgraph[k][j];}}vis[minid]1;// 更新// 根据这个点更新其他所有距离for(int j1;jgraph.size();j){graph[k][j]min(graph[k][j],graph[k][minid] graph[minid][j]);}}int ans0;for(int i1;i graph.size();i){if(graph[k][i]INT_MAX) return -1;ansmax(ans, (int)graph[k][i]);}return ans;
}
int main()
{vectorvectorint times{{2,1,1},{2,3,1},{3,4,1}};int rsnetworkDelayTime(times,4,2);coutrsendl;}dijstra 稀疏图(邻接表) -我更喜欢的方式!!!
求点k到其他点的距离
与上面不同的情况是, 采用邻接表最小堆
最小堆 的格式是(点k到该点的距离,该点的id)
dis[] 存储的是点k到达每个点的最短距离
st[] 存储的是否能确定点k到达每个点的距离while(队列不为空)
{队列弹出一个如果该点确定了最短距离,就不管它 if(st[]) continue把弹出的这个点加入最短距离根据这个点进行扩展,遍历这个点指向其他点的边如果比div小,则更新距离加入队列中
}typedef long long ll;
typedef pairll,ll pll;
struct Edge
{int next;int val;Edge(int next_,int val_):next(next_),val(val_){;}
};
class Solution {
public:int networkDelayTime(vectorvectorint times, int n, int k) {vectorvectorEdge graph(n1);for(auto item:times){int aitem[0];int bitem[1];int citem[2];graph[a].push_back(Edge(b,c));}vectorll dis(graph.size(),INT_MAX);vectorint st(graph.size(),0);priority_queuepll,vectorpll,greaterpll ls;ls.push(pll(0,k));dis[k]0;while(ls.size()){auto itemls.top();ls.pop();ll distanceitem.first;int iditem.second;// 保证未加入if(st[id]) continue;// 加入st[id]1;// 扩展更新for(int i0;igraph[id].size();i){// k-id-id2// distance distance2int id2graph[id][i].next;int distance2graph[id][i].val;if(distancedistance2dis[id2]){dis[id2]distancedistance2;// 加入队列ls.push(pll(dis[id2],id2));}}}int rs(int)*max_element(dis.begin()1,dis.end());if(rsINT_MAX) return -1;else return rs;}
};
