优秀企业网站的特点,flash 网站欣赏,秀米官网登录入口,深圳龙岗区吉华街道邮编目录 先分个类吧#xff1a;
1.对于有向无环图#xff0c;我们直接拓扑排序#xff0c;和AOE网类似#xff0c;把取max改成min即可。
2.边权全部相等#xff0c;直接BFS即可
3.单源点最短路
从一个点出发#xff0c;到达其他顶点的最短路长度。
Dijkstra算法#x…目录 先分个类吧
1.对于有向无环图我们直接拓扑排序和AOE网类似把取max改成min即可。
2.边权全部相等直接BFS即可
3.单源点最短路
从一个点出发到达其他顶点的最短路长度。
Dijkstra算法用于一个节点到所有其他节点的最短路。要求不存在负权边可以用于无向图 先分个类吧
1.对于有向无环图我们直接拓扑排序和AOE网类似把取max改成min即可。
2.边权全部相等直接BFS即可
3.单源点最短路
从一个点出发到达其他顶点的最短路长度。 基本操作松弛d[u]wd[v]于是距离更改。
Dijkstra算法用于一个节点到所有其他节点的最短路。要求不存在负权边可以用于无向图
具体过程
1.开始之前认为所有点都未计算dis[]全部赋为极大值。
2.源点的dis[]0;
3。计算与源点相邻的所有点的dismap[s][v];
4.在还未算出最短路点的dis中选出最小一个点u,显然因为不存在负权边它的最短路就是dis.
5.对于与u相连的所有点v若dis[u]map[u][v]比当前的dis小就松弛更新。
6.重复上述45操作。
正确性证明
其实就是每一次贪心显然从源点开始的第一步得到的最短的路肯定就是最短路到它的其他路肯定比它长。
当我们把除源点外第一个确定的加入后我们再用它去更新一下它连的点。
然后我们选其中最小的点它就是确定的。因为要走到它要么从那些没有确定最小路的点出发到它因为这点是最小的点无负权边因此这样的点距离肯定更大要么从已经确定的点上拓展出来又因为他们不断地更新松弛每一个确定最小路的点加入后我们再用它去更新一下它连的点所以我们可以保证在已经确定地点到最小的点的路径是最优的。因此我们保证最小的点它就是确定的。
下面放一道模板题 下面是AC代码注意无向边建图edge要2倍
#includebits/stdc.h
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator(const ty a) const{return dis1a.dis1;}
};
void merge(int x,int y,int v){edge[cnt].zhiv;edge[cnt].diany;edge[cnt].nexthead[x];head[x]cnt;
}
priority_queuety q;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ckq.top();q.pop();if(vis[ck.dian]1) continue;vis[ck.dian]1;for(int ihead[ck.dian];i!-1;iedge[i].next){int i1edge[i].dian;if(vis[i1]1) continue;if(dis[i1]dis[ck.dian]edge[i].zhi){dis[i1]dis[ck.dian]edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cinnm1st;memset(head,-1,sizeof(head));for(int i1;im1;i){scanf(%d%d%d,x,y,v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]0;coutdij(s,t);
}
