Dijstra算法的代码实现及解释（最短路径问题）

/*Dijstra 算法 实践
begin date：2015.3.19
end date：2015.3.19*/

#include<iostream>
using namespace std;
const int max = 10000000;

/*伪码：
class 图
creat ()构造一个动态矩阵,将所有点赋值接近无穷大。
set（）输入各点及权值
void Dijstra：
1.历遍一次起点找最短路径；
2.记录新收入的节点
3.更新dist距离和路径；
*/


class graph
{
public:
	graph(int n, int e)
	{
		node = n;
		edge = e;
	}
	void creat_graph();//初始化动态二维矩阵
	void set_graph();//赋予权值
	void Dijstra(int);//最短路径算法
	void show_Dijstra(int);//显示起始点到各点的距离
	friend void test(graph);//测试矩阵
private:
	int node;
	int edge;
	int **G;
};

//用作测试的友元函数，输出可达矩阵
void test(graph gg)
{
	for (int i = 0; i < gg.node; i++)
	{
		for (int j = 0; j < gg.node; j++)
		{
			if ((gg.G)[i][j]!=max)
			cout << (gg.G)[i][j] << ' ';
			else cout << 0 << ' ';
		}cout << endl;
	}
}

void graph::creat_graph()                   //建立一个动态二维数组
{
	G = new int*[node];
	for (int i = 0; i < node; i++)
		G[i] = new int[node];
	for (int i = 0; i < node; i++)
	{
		for (int j = 0; j < node; j++)
		{
			G[i][j] = max;                  //各个权值赋无穷大，表示不可达；
		}
	}
}
void graph::set_graph()                     //输入可达的点和权值，建立无向图；
{
	int i , j , w;
	int t=edge;
	for (; t>0; t--)
	{
		cin >> i >> j >> w;
		G[i][j] = w;
		G[j][i] = w;
	}
}
/*PS:若想建立有向图，可将G【j】【i】=w注释掉，是矩阵不具备对称性*/

void graph::Dijstra(int s)                    
{
	bool *visited = new bool[node];//visited数组用于记录被访问并记入的点，避免起点被重复访问
	for (int i = 0; i < node; i++)
		visited[i] = false;
	visited[s] = true;//源节点被记录已访问和记入
	for (int i = 0; i < node-1; i++)
	{
			int min = max;
			int record;//记录新记录的点
			for (int j = 0; j < node; j++)
			{
				if (visited[j] == false && G[s][j] < min)//找出 未记录的点中到源节点有最短距离的点
				{
					min = G[s][j];
					record = j;		
				}
			}
			visited[record] = true;//记录有最短距离的点
			for (int j = 0; j < node; j++)//更新路径和源节点到各个可达节点的最短距离
			{
				if (visited[j] == false && min + G[record][j] < G[s][j])
				{
					G[s][j] = min + G[record][j];
					G[j][s] = min + G[record][j];//同样在有向图中要将此句注释掉
				}
			}
	}
	delete []visited;
}

void graph::show_Dijstra(int s)
{
	for (int i = 0; i < node; i++)
	{
		if (i != s)
			cout << s << "->" << i << ' '<<G[s][i] << endl;
	}
}

int main()
{
	int n, e;
	while (cin >> n >> e)
	{
		int s;
		graph g(n, e);
		g.creat_graph();
		g.set_graph();
		cout << "Start point:";
		while (cin >> s)
		{
			g.Dijstra(s);
			g.show_Dijstra(s);
			test(g);//测试
		}
	}
	return 0;
}
           

测试数据：
           

<img src="https://img-blog.csdn.net/20150319210900296?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjE1Njc5MDM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
           

调试结果：
           

<img src="https://img-blog.csdn.net/20150319205943056?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjE1Njc5MDM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />