江苏平台网站建设价位,成都市建设领域网站咨询电话,手机网站如何排版,网站建设需要用到什么软件对fill用法的介绍
1.用邻接矩阵实现
const int maxn100;
const int INF100000000;//无穷大#xff0c;用来初始化边
int G[maxn][maxn];//用邻接矩阵存储图的信息
int isin[maxn]{false};//记录是否已被访问
int minDis[maxn];//记录到顶点的最小距离void Dijkstra(int s,in…对fill用法的介绍
1.用邻接矩阵实现
const int maxn100;
const int INF100000000;//无穷大用来初始化边
int G[maxn][maxn];//用邻接矩阵存储图的信息
int isin[maxn]{false};//记录是否已被访问
int minDis[maxn];//记录到顶点的最小距离void Dijkstra(int s,int num){fill(minDis,minDisnum,INF);//先无穷大覆盖minminDis[s]0;//令起始结点为0for(int i0;inum;i){//记录最短距离及其对应下标:先初始化为最小int mINF,centra-1;for(int j0;jnum;j){//若未被访问且到顶点的最短距离最小if(isin[j]falseminDis[j]m){//更新最短距离及其下标mminDis[j];centraj;}}//找不到最小的顶点了说明此时剩余结点与顶点连通无关INF说明已结束if(centra-1) return;isin[centra]true;//开放与centra有关的顶点,并更新其当前到顶点的最小距离for(int k0;knum;k){if(isin[k]falseG[centra][k]!INFG[centra][k]minDis[centra]minDis[k])minDis[k]G[centra][k]minDis[centra];}}
}记录最短路径
添加一个记录结点的数组即可将它记录最短路径的结点的前一个结点
const int maxn100;
const int INF100000000;//无穷大用来初始化边
int G[maxn][maxn];//用邻接矩阵存储图的信息
int isin[maxn]{false};//记录是否已被访问
int minDis[maxn];//记录到顶点的最小距离
int pre[maxn];//记录最短路径void Dijkstra(int s,int num){fill(minDis,minDisnum,INF);//先无穷大覆盖minminDis[s]0;//令起始结点为0for(int i0;inum;i)pre[i]i;//初始化为自身for(int i0;inum;i){//记录最短距离及其对应下标:先初始化为最小int mINF,centra-1;for(int j0;jnum;j){//若未被访问且到顶点的最短距离最小if(isin[j]falseminDis[j]m){//更新最短距离及其下标mminDis[j];centraj;}}//找不到最小的顶点了说明此时剩余结点与顶点连通无关INF说明已结束if(centra-1) return;isin[centra]true;//开放与centra有关的顶点,并更新其当前到顶点的最小距离for(int k0;knum;k){if(isin[k]falseG[centra][k]!INFG[centra][k]minDis[centra]minDis[k]){minDis[k]G[centra][k]minDis[centra];//记录最短距离pre[k]u;//记录最短路径的前驱结点}}
}
void minPath(int begin,int now){//输出if(nowbegin)//回溯到起点{coutbegin;return;//跳到下一层}minPath(begin,pre[now]);coutnow;//从起点后不断往外输出结点}2.用邻接表实现
#include vector
using namespace std;
const int maxn100;
const int INF10000000000;
bool isin[maxn]{false};
int path[maxn];
struct node{int id;//结点编号int value;//结点的边权
}nodes;
vectornode v[maxn];void Dijisktra(int s,int num){int m,mp;fill(path,pathnum,INF);path[s]0;for(int i0;inum;i){mpINF;m-1;for(int j0;jnum;j){if(isin[j]falsepath[j]mp){mj;mppath[j];}}if(m-1) return;isin[m]true;//只有这里与邻接矩阵不同因为邻接表存储结点信息的方式不同 for(int k0;knum;k){//v[m][k]-指的是顶点m中第k1个与m相连的结点int indexv[m][k].id;if(isin[index]falsev[m][k].valuemppath[index])path[index]v[m][k].valuemp;}}
}模拟简单实现
#include iostream
using namespace std;
const int maxn100;
const int INF10000000;
bool isin[maxn]{false};
int G[maxn][maxn],num,edge,begins;
int path[maxn];void Dijisktra(int s){fill(path,pathnum,INF);path[s]0;for(int i0;inum;i){int m-1,nINF;for(int j0;jnum;j){if(isin[j]falsepath[j]n){mj;npath[j];}}if(m-1) return;isin[m]true;for(int k0;knum;k){if(isin[k]falseG[m][k]!INFG[m][k]path[m]path[k])path[k]G[m][k]path[m];}}
}
int main(){int v1,v2,weight;cinnumedgebegins;fill(G[0],G[0]maxn*maxn,INF);//初始为无穷for(int i0;iedge;i){cinv1v2weight;G[v1][v2]weight;}Dijisktra(begins);for(int i0;inum;i)if(i!num-1)coutpath[i] ;else coutpath[i]endl;return 0;
}
