数据结构__dijksra算法

注释很详尽了：

#include<iostream>
#include<vector>
#define maxn 1000//最大节点数
#define inf 1000000000//模拟距离无限大
int G[maxn][maxn];//邻接阵，用于比较时提取G[u][v]
using namespace std;

struct node
{
	int adjvex;//节点序号
	char data;//节点英文字母
	int weight;//权重
};

vector<node> adj[maxn];//定义邻接表
int n;//定点数

//邻接表节点创建
void createNode(char a,int i,int w=0)
{
	node temp;
	temp.adjvex = a-'a';
	temp.data = a;
	temp.weight = w;
	adj[i].push_back(temp);
}

//邻接表键入
void create()
{
	int m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		char tempA;
		cin >> tempA;
		createNode(tempA, i);
	}
	char a, b;
	int cost,aa,bb;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> cost;
		for (int j = 0; j < n; j++)
		{
			if (a == adj[j][0].data)
				aa = adj[j][0].adjvex;
			if (b == adj[j][0].data)
				bb = adj[j][0].adjvex;
		}
		G[aa][bb] = cost;
		createNode(b, aa, cost);
	}
}

//打印邻接表
void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			cout << adj[i][j].data <<adj[i][j].weight << ' ';
		}
		cout << endl;
	}
}

int d[maxn];//起点到达各点的最短路径长度
bool vis[maxn] = { false };//标记数组是否被访问

void dijkstra(int s)//s为起点
{
	fill(d, d + maxn, inf);//初始化d数组全为inf
	d[s] = 0;//起点到自身距离
	for (int i = 0; i < n; i++)//循环n趟
	{
		int u = -1, min = inf;//u使d[u]最小min存放最小的d[u]
		for (int j = 0; j < n; j++)
		{
			if (vis[j] == false && d[j] < min)
			{
				u = j;
				min = d[j];
			}
		}
		if (u == -1)return;//找不到与s相同的节点了，结束该函数
		vis[u] = true;//标记u为已访问
		for (int j=0;j<adj[u].size();j++)
		{
			int v = adj[u][j].adjvex;//通过邻接表获得u能访问的节点v
			if (vis[v] == false && d[u] + adj[u][j].weight < d[v])
				d[v] = d[u] + adj[u][j].weight;//贪心，使得更优化
		}
	}
}

int main(void)
{
	create();
	print();
	fill(G[0], G[0] + maxn * maxn, inf);
	char s;
	cin >> s;
	int ss;
	for (int j = 0; j < n; j++)
	{
		if (s == adj[j][0].data)
			ss = adj[j][0].adjvex;
	}
	dijkstra(ss);
	for (int i = 0; i < n; i++)
		cout <<adj[i][0].data <<':'<< d[i]<<' ';
	cout << endl;
	system("pause");
	return 0;
}

一组测试i/o：