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="" />