數據結構(c++)(第二版) Dijkstra最短路徑算法 教學示範代碼出現重大問題!

前言

去年在數據結構(c++)的Dijkstra教學算法案例中,發現了一個 bug 導致算法不能正常的運行,出錯代碼只是4行的for循環迭代代碼。

看到那裡就覺得有問題,但書中只給了關鍵代碼的部分,其餘皆是偽代碼,做偽代碼實現,運行了教學代碼,證實了相關錯誤。也給出了能正確運行的for循環迭代代碼。

之後便將過程發給出版社,可一年多了,出版社也沒有回信……

image

也希望大家也可以討論一下。

Dijkstra最短路徑算法

Dijkstra最路徑算法用於求單源點最短路徑問題,問題描述如下:給定帶權有向圖G=(V,E)和源點v屬於V,求從v到G中其餘各頂點的最短路徑。

單源點最短路徑問題的一個應用實例是關於計算機網絡傳輸的問題:怎樣找到一種最經濟的方式,從一台計算機向網上所有其他計算機發送一條消息。

Dijkstra算法是應用貪心法進行算法設計的一個典型例子。

問題

數據結構(c++)(第二版) 版次:2011年6月第2版 印次:2020年1月第25次印刷 清華大學出版社

書中的Dijkstra的實列代碼(P170-171)出現了’k’無法更新的錯誤,代碼無法得到最後的正確結果。

‘k’是dist[n]中最小值的下標,所以每次’k’的更新都要從S集合之外去尋找,而書中是以 k=0 去更新,在k=0的條件約束下,根本無法進入k的更新,所以在運行了4次之後會退出while() 沒有辦法更新。

希望貴出版社能夠思考,若確實有錯誤希望貴出版社能夠修正此代碼。

image

#include <iostream>
#include <cstring>
using namespace std;
const int Max=9999;
class MGraph
{
	int arc[5][5];		//鄰接矩陣  
	string vertex[10];	//圖的頂點 
	int vertexNum;
public:
	MGraph();				//初始化鄰接矩陣 對角元素為0 其他元素為Max 
	void Input();      		//輸入書中的 6 -28 進行測試 
	void Show();
	friend void Dijkastra( MGraph G , int v );
};
MGraph::MGraph()
{
	int i,j;
	vertexNum=5;
	vertex[0]='a';    //等同於 V0 
	vertex[1]='b';
	vertex[2]='c';
	vertex[3]='d';
	vertex[4]='e';
	vertex[5]='\0';
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			arc[i][j]=Max;
			if(i==j) arc[i][j]=0;
		}
	}
}
void MGraph::Input()
{
	int i,j,d;
	cout<<"請按順序輸入 本書 圖 6-28 (b)鄰接矩陣的 行 列  權值 輸入的行列大於等於5退出"<<endl;
	cin>>i>>j>>d;
	while((i<5)&&(j<5))
	{
		arc[i][j]=d;
		cout<<"請按順序輸入 鄰接矩陣的 行 列  權值"<<endl; 
		cin>>i>>j>>d;
	}
}
void MGraph::Show()
{
	int i,j;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {
            cout<<arc[i][j]<<"		";
        }
        cout<<endl;
    }
}
void Dijkastra( MGraph G , int v )
{
	int i=0,k;
	int dist[10];
	int s[5];
	int num;
	string path[10];
	for (i=0; i<G.vertexNum; i++)
	{
		dist[i]=G.arc[v][i];
		if (dist[i]!=Max) path[i]=G.vertex[v]+G.vertex[i];
		else path[i]="";
	}
	s[0]=v;			//初始化集合 S 
	dist[v]=0;		//標記頂點 v 為源點 
	num=1;
	while(num<G.vertexNum)					//當頂點數num小於圖的頂點數 
	{
		// 使用時 這兩個for循環使用其中一個 即可得到對應結果
		
		// 可以成功實現的迭代代碼
		/*for(i=0;i<G.vertexNum;i++)       		//修改後的 k 的迭代    ************************************* 
		{
			if(dist[i]!=0) 
			{
				k=i;
				break;
			}
		}*/
		
		// 書中的教學代碼
		for(i=0;i<G.vertexNum;i++) 		//在dist中查找最小元素        ** k 無法更新! 
		{
			if((dist[i]!=0)&&(dist[i]<dist[k])) k=i;
		}
		
		
		cout<<dist[k]<<" "<<path[k]<<endl;
		s[num++]=k;							//將生成的重點加入集合S 
		for(i=0;i<G.vertexNum;i++)			//修改數組dist和path 
		{
			if(dist[i]>dist[k]+G.arc[k][i])
			{
				dist[i]=dist[k]+G.arc[k][i];
				path[i]=path[k]+G.vertex[i];
			}
		}
		dist[k]=0;		//置頂點k 為已生成頂點標記 
	}
}
int main(int argc, char** argv) 
{
	MGraph G;
	G.Input();
	G.Show();
	Dijkastra(G,0);
	return 0;
}

改正後的代碼

image

教材示例代碼

image

Tags: