dijkstra算法（二）：邻接表表示法

边的表示问题：

图的表示一般有两种：邻接表和邻接矩阵表示，邻接表表示法的空间开销比较小，但对于点少边多的情况则不太适用。其空间复杂度为O（n+e）。如果e达到n²数量接的时候，，邻接矩阵则比较适合。空间复杂度只取决于顶点的数量n。空间复杂度为O(n²)。

邻接表的实现思路：

可以构造一个结构体，成员为每一条边的终点v和权重w。然后开一个结构体数组edge[maxn]。用head[u]（u为顶点）数组来指向每一组起点相同的边的链表。

dijkstra算法（双向）：

#include<iostream>
#include<queue>
#define INF 0x3f3f3f

using namespace std;
const int maxn = 200005;  //边的数目较多
int head[10005];
int dis[10005];
bool vis[10005];
int cnt = 0;

struct qnode
{
	int u;  //起点
	int w;  //边的长度（权重）
	qnode(int u,int w):u(u),w(w){}
	bool operator < (const qnode b) const
	{
		return w > b.w;
	}
};

struct Edge
{
	int v;    //边的终点
	int w;
	int mext;    //指向下一条边
}edge[maxn];

void add_edge(int u,int v,int w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].mext = head[u];
	head[u] = cnt;
	cnt++;
}
priority_queue<qnode> p;

void dijkstra(int s)
{
	int u, v, w;
	int i;
	while (!p.empty())
		p.pop();
	p.push(qnode(s, 0));
	dis[s] = 0;
	while (!p.empty())
	{
		qnode q = p.top();
		p.pop();
		u = q.u;
		w = q.w;
		if (!vis[u])
			continue;
		vis[u] = false;
		for (i = head[u]; i != -1; i = edge[i].mext)
		{
			v = edge[i].v;
			w = edge[i].w;
			if (vis[v] && dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				p.push({ v, dis[v] });
			}
		}
	}
}

int main()
{
	for (int i = 0; i < 10005; i++)
	{
		vis[i] = true;
		dis[i] = INF;
		head[i] = -1;
	}
	int m, s, t;
	int u, v, w;
	cout << "请输入边的数目,起点,终点：" << endl;
	cin >> m >> s >> t;
	cout << "请输入边的起点，终点，权重：" << endl;
	while (m--)
	{
		cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	dijkstra(s);
	if (dis[t] != INF)
		cout << dis[t] << endl;
	else
		cout << "No Path!" << endl;
	return 0;
}

测试实例：

输入：

请输入边的数目,起点,终点：
7 1 5
请输入边的起点，终点，权重：
1 4 4
1 3 2
1 5 7
2 5 10
2 3 1
3 5 2
4 3 7

输出：

4

dijkstra算法（单向）：

#include<iostream>
#include<queue>
#define INF 0x3f3f3f

using namespace std;
const int maxn = 200005;  //边的数目较多
int head[10005];
int dis[10005];
bool vis[10005];
int cnt = 0;

struct qnode
{
	int u;  //起点
	int w;  //边的长度（权重）
	qnode(int u,int w):u(u),w(w){}
	bool operator < (const qnode b) const
	{
		return w > b.w;
	}
};

struct Edge
{
	int v;    //边的终点
	int w;
	int mext;    //指向下一条边
}edge[maxn];

void add_edge(int u,int v,int w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].mext = head[u];
	head[u] = cnt;
	cnt++;
}
priority_queue<qnode> p;

void dijkstra(int s)
{
	int u, v, w;
	int i;
	while (!p.empty())
		p.pop();
	p.push(qnode(s, 0));
	dis[s] = 0;
	while (!p.empty())
	{
		qnode q = p.top();
		p.pop();
		u = q.u;
		w = q.w;
		if (!vis[u])
			continue;
		vis[u] = false;
		for (i = head[u]; i != -1; i = edge[i].mext)
		{
			v = edge[i].v;
			w = edge[i].w;
			if (vis[v] && dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				p.push({ v, dis[v] });
			}
		}
	}
}

int main()
{
	for (int i = 0; i < 10005; i++)
	{
		vis[i] = true;
		dis[i] = INF;
		head[i] = -1;
	}
	int m, s, t;
	int u, v, w;
	cout << "请输入边的数目,起点,终点：" << endl;
	cin >> m >> s >> t;
	cout << "请输入边的起点，终点，权重：" << endl;
	while (m--)
	{
		cin >> u >> v >> w;
		add_edge(u, v, w);  //单向
	}
	dijkstra(s);
	if (dis[t] != INF)
		cout << dis[t] << endl;
	else
		cout << "No Path!" << endl;
	return 0;
}

测试实例2：

输入：

请输入边的数目,起点,终点：
11 0 1
请输入边的起点，终点，权重：
0 1 50
0 2 10
0 4 45
1 2 15
1 4 5
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 3

输出：

45