传统的dijkstra算法是维护一个集合和一个数组

在算法开始的时候，我们有一个集合X和一个数组dis. 起初将起点s加入集合，然后起点到起点的最短距离是0，dis[s] = 0;  接着我们不断的在剩下的顶点中找到一个离X最近的点v，并将该点加入到X中，然后更新dis。更新dis的原理是，比较原来到所有点到X的s的距离和新的可能通过新加入的点v产生的最短距离，取两者中较小的一个。这样当把所有的点都加入到X后就求出了所有点到s的最短距离，并保存在dis数组中。

code：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000 + 7;

int cost[MAXN][MAXN];	// cost[u][v]表示u->v这条边的权值，不存在设为INF 
int dis[MAXN];			// 顶点从s出发的最短距离 
bool used[MAXN];		// 已经使用过的顶点 
int V;		// 顶点个数

// 求从s出发到各个顶点的最短距离
void djk(int s)
{
	memset(dis, 0x3f, sizeof(dis));
	memset(used, 0, sizeof(used));
	dis[s] = 0;		// 起点到自身的最短距离为0
	
	while(true)
	{
		int v = -1;
		for(int u = 0; u < V; u++)		// 从尚未使用过的顶点中选择一个距离最小的顶点 
			if( !used[u] && (v == -1 || dis[u] < dis[v]))	
				v = u;
		if(v == -1)		// 没有顶点可选 
			break;
		used[v] = true;
		for(int u = 0; u < V; u++)		// 更新最短距离，比较已知的最短距离和可能通过v产生的新的最短距离 
			dis[u] = min(dis[u], dis[v] + cost[v][u]);
	} 
} 

int main()
{
	
	
	
	
	return 0;
}

上面用邻接矩阵实现的dijkstra算法的复杂度是O(n^2), 下面是用优先队列和邻接表实现的dijkstra算法。复杂度O(E * log(v))。

code:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1000 + 7;

struct Edge{
	int to, cost;
};
typedef pair<int, int> Pair;	// first 是起点到其他顶点的最短距离, second顶点的编号 

int V;
vector<Edge> G[MAXN];
int dis[MAXN];

void dijkstra(int st)
{
	priority_queue<Pair, vector<Pair>, greater(Pair)> que;	// 堆按照first从小到大的顺序取值 
	memset(dis, 0x3f, sizeof(dis));
	dis[st] = 0;
	que.push(Pair(0, st));	// 把起点放入队列
	
	while( !que.empty()) 
	{
		Pair p = que.top();
		que.pop();
		int v = p.second;
		if(dis[v] < p.first)
			continue;
		for(int i = 0; i < G[v].size(); i++)
		{
			Edge e = G[v][i];
			if(dis[e.to] > dis[v] + e.cost)
			{
				dis[e.to] = dis[v] + e.cost;
				que.push(P(dis[e.to], e.to));
			}
		} 
	}
	
}


int main()
{
	
	
	
	
	return 0;
}