Dijkstra 迪杰斯特拉算法 邻接矩阵版和邻接表版 核心代码

Dijkstra 算法 

Dijstra(G,d[],s){
	
	初始化;
	for(循环n次){
		u=使d[u]最小的还未被访问的顶点的标号
		记u已被访问
		for(从u出发的能到达的所有结点v){
			if(v未被访问&&以u为中介点使s到达v的最短距离d[v]更优)
				优化d[v]; 
		} 
	}
} 

const int maxn=1000;	//最大顶点 
const int INF=1000000000;


//-------------------------------------// 
//邻接矩阵 适用于V<1000
//时间复杂度 O(V**(V+V))=O(V^2) 

int n,G[maxn][maxn];
int d[maxn];	//起点到各点的最短路径
bool vis[maxn]={false};

void Dijkstra(int s){
	//慎用memset 
	fill(d,d+maxn,INF);
	d[s]=0;
	
	for(int i=0;i<n;i++){
		int u=-1,min=INF;
		
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<min){
				u=j;
				min=d[j];
			}
		}
		
		//找不到说明剩下的不连通 
		if(u==-1)	return ;
		vis[u]=true;
		
		//优化d[v] 
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INFd[u]+G[u][v]<d[u]){
				d[v]=d[u]+G[u][v];
			}
		} 	
	} 
		
} 


//-------------------------------------// 
//邻接表 
//时间复杂度 O(V^2+E)

struct Node{
	int v,dis;	//v为目标结点，dis为边权 
}; 
vector<Node> Adj[maxn];

int n;
int d[maxn];
bool vis[maxn]={false};

void Dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	
	for(int i=0;i<n;i++){
		int u=-1,min=INF;
		
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<min){
				u=j;
				min=d[j];
			}
		}
		
		//找不到说明剩下的不连通 
		if(u==-1)	return ;
		vis[u]=true;
		
		for(j=0;j<Adj[u].size();j++){
			int v=Adj[u][j].v;
			if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
				d[v]=d[u]+Adj[u][j].dis;
			}
		}
}