求最短路径之迪杰斯特拉算法

对fill用法的介绍

1.用邻接矩阵实现

const int maxn=100;
const int INF=100000000;//无穷大，用来初始化边
int G[maxn][maxn];//用邻接矩阵存储图的信息
int isin[maxn]={false};//记录是否已被访问
int minDis[maxn];//记录到顶点的最小距离void Dijkstra(int s,int num){fill(minDis,minDis+num,INF);//先无穷大覆盖minminDis[s]=0;//令起始结点为0for(int i=0;i<num;i++){//记录最短距离及其对应下标:先初始化为最小int m=INF,centra=-1;for(int j=0;j<num;j++){//若未被访问且到顶点的最短距离最小if(isin[j]==false&&minDis[j]<m){//更新最短距离及其下标m=minDis[j];centra=j;}}//找不到最小的顶点了，说明此时剩余结点与顶点连通，无关INF，说明已结束if(centra==-1) return;isin[centra]=true;//开放与centra有关的顶点,并更新其当前到顶点的最小距离for(int k=0;k<num;k++){if(isin[k]==false&&G[centra][k]!=INF&&G[centra][k]+minDis[centra]<minDis[k])minDis[k]=G[centra][k]+minDis[centra];}}
}

记录最短路径

添加一个记录结点的数组即可，将它记录最短路径的结点的前一个结点

const int maxn=100;
const int INF=100000000;//无穷大，用来初始化边
int G[maxn][maxn];//用邻接矩阵存储图的信息
int isin[maxn]={false};//记录是否已被访问
int minDis[maxn];//记录到顶点的最小距离
int pre[maxn];//记录最短路径void Dijkstra(int s,int num){fill(minDis,minDis+num,INF);//先无穷大覆盖minminDis[s]=0;//令起始结点为0for(int i=0;i<num;i++)pre[i]=i;//初始化为自身for(int i=0;i<num;i++){//记录最短距离及其对应下标:先初始化为最小int m=INF,centra=-1;for(int j=0;j<num;j++){//若未被访问且到顶点的最短距离最小if(isin[j]==false&&minDis[j]<m){//更新最短距离及其下标m=minDis[j];centra=j;}}//找不到最小的顶点了，说明此时剩余结点与顶点连通，无关INF，说明已结束if(centra==-1) return;isin[centra]=true;//开放与centra有关的顶点,并更新其当前到顶点的最小距离for(int k=0;k<num;k++){if(isin[k]==false&&G[centra][k]!=INF&&G[centra][k]+minDis[centra]<minDis[k]){minDis[k]=G[centra][k]+minDis[centra];//记录最短距离pre[k]=u;//记录最短路径的前驱结点}}
}
void minPath(int begin,int now){//输出if(now==begin)//回溯到起点{cout<<begin;return;//跳到下一层}minPath(begin,pre[now]);cout<<now;//从起点后不断往外，输出结点}

2.用邻接表实现

#include <vector>
using namespace std;
const int maxn=100;
const int INF=10000000000;
bool isin[maxn]={false};
int path[maxn];
struct node{int id;//结点编号int value;//结点的边权
}nodes;
vector<node> v[maxn];void Dijisktra(int s,int num){int m,mp;fill(path,path+num,INF);path[s]=0;for(int i=0;i<num;i++){mp=INF;m=-1;for(int j=0;j<num;j++){if(isin[j]==false&&path[j]<mp){m=j;mp=path[j];}}if(m==-1) return;isin[m]=true;//只有这里与邻接矩阵不同，因为邻接表存储结点信息的方式不同 for(int k=0;k<num;k++){//v[m][k]-指的是顶点m中第k+1个与m相连的结点int index=v[m][k].id;if(isin[index]==false&&v[m][k].value+mp<path[index])path[index]=v[m][k].value+mp;}}
}

模拟简单实现

#include <iostream>
using namespace std;
const int maxn=100;
const int INF=10000000;
bool isin[maxn]={false};
int G[maxn][maxn],num,edge,begins;
int path[maxn];void Dijisktra(int s){fill(path,path+num,INF);path[s]=0;for(int i=0;i<num;i++){int m=-1,n=INF;for(int j=0;j<num;j++){if(isin[j]==false&&path[j]<n){m=j;n=path[j];}}if(m==-1) return;isin[m]=true;for(int k=0;k<num;k++){if(isin[k]==false&&G[m][k]!=INF&&G[m][k]+path[m]<path[k])path[k]=G[m][k]+path[m];}}
}
int main(){int v1,v2,weight;cin>>num>>edge>>begins;fill(G[0],G[0]+maxn*maxn,INF);//初始为无穷for(int i=0;i<edge;i++){cin>>v1>>v2>>weight;G[v1][v2]=weight;}Dijisktra(begins);for(int i=0;i<num;i++)if(i!=num-1)cout<<path[i]<<" ";else cout<<path[i]<<endl;return 0;
}