題目描述

用鄰接矩陣存儲(chǔ)有向圖，實(shí)現(xiàn)最短路徑Dijkstra算法，圖中邊的權(quán)值為整型，頂點(diǎn)個(gè)數(shù)少于10個(gè)。

部分代碼提示：
#include
#include
using namespace std;

const int MaxSize = 10;
const int INF = 32767;

class MGraph
{
public:
MGraph(char a[], int n, int e);

void Dijkstra();

private:
char vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};

MGraph::MGraph(char a[], int n, int e)
{
//write your code.

}

int Min(int dist[], int vertexNum)
{
//write your code.

}
void MGraph::Dijkstra()
{
//write your code.

}

int main()
{
int n = 0;
int e = 0;
cin >> n >> e;
char p[MaxSize];
int i = 0;

for (i=0; i<n; i++)
{
	cin >> p[i];
}

MGraph MG(p, n, e);

MG.Dijkstra();

return 0;

}

輸入描述

首先輸入圖中頂點(diǎn)個(gè)數(shù)和邊的條數(shù)；
再輸入頂點(diǎn)的信息（字符型）；
再輸入各邊及其權(quán)值。

輸出描述

依次輸出從編號(hào)為0的頂點(diǎn)開始的從小到大的所有最短路徑，每條路徑及其長(zhǎng)度占一行。

輸入樣例

5 7
A B C D E
0 1 6
0 2 2
0 3 1
1 2 4
1 3 3
2 4 6
3 4 7

輸出樣例

AD 1
AC 2
AB 6
ADE 8
內(nèi)存閥值:50240K 耗時(shí)閥值:5000MS文章來源地址http://www.zghlxwxcb.cn/news/detail-428824.html

代碼

#include <iostream>
#include <string>
using namespace std;
 
const int MaxSize = 10;
const int INF = 32767;
 
class MGraph
{
public:
	MGraph(string a[], int n, int e);
 
	void Dijkstra();
 
private:
	string vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum, arcNum;
};
 
MGraph::MGraph(string a[], int n, int e)
{
	//1、賦值
	vertexNum = n;
	arcNum = e;
	//2、頂點(diǎn)表
	for (int i = 0; i < vertexNum; i++)
		vertex[i] = a[i];
	//3、邊表初始化
	for (int i = 0; i < vertexNum; i++)
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = INF;
	//4、邊表賦值
	int i = 0, j = 0, w = 0;
	for (int k = 0; k < arcNum; k++)
	{
		cin >> i >> j >> w;
		arc[i][j] = w;
		//arc[j][i] = w;//有方向的不用反復(fù)設(shè)置相同！?。?！掉坑了我淦！
	}
}
 
int Min(int dist[], int vertexNum)
{
	int min = INF;
	
	int pos = 0;
 
	for (int i = 0; i < vertexNum; i++)
	{
		if (dist[i] < min && dist[i] != 0)//!=0?:存入的頂點(diǎn)不需要遍歷
		{
			min = dist[i];
 
			pos = i;
		}
	}
	return pos;
}
 
void MGraph::Dijkstra()
{
	int v = 0;
	int i, k, num, dist[MaxSize];//權(quán)值表
	string path[MaxSize];//路徑表
	for (i = 0; i < vertexNum; i++)
	{
		dist[i] = arc[v][i];//v-表示當(dāng)前頂點(diǎn)，i-表示這個(gè)頂點(diǎn)與其他頂點(diǎn)的邊的權(quán)值（希望屏幕前的你能理解）
 
		if (dist[i] != INF)//如果連通
			path[i] = vertex[v] + vertex[i];
		else
			path[i] = "";
	}
 
	dist[0] = 0;
	
	for (num = 1; num < vertexNum; num++)//不知道為什么=1？頂點(diǎn)表已經(jīng)在集合中了，所以不用遍歷
	{
		k = Min(dist, vertexNum);
		
		cout << path[k] <<' ' << dist[k];
 
		for (i = 0; i < vertexNum; i++)//更新最小權(quán)值表
		{
			if (dist[i] > dist[k] + arc[k][i])
			{
				dist[i] = dist[k] + arc[k][i];
 
				path[i] = path[k] + vertex[i];
			}
		}
		dist[k] = 0;//將k加入集合，為什么是0？因?yàn)?比其他路徑權(quán)值和都要小所以無法改變
	}
}
 
int main()
{
	int n = 0;
	int e = 0;
	cin >> n >> e;
	string p[MaxSize];
	int i = 0;
 
	for (i = 0; i < n; i++)
	{
		cin >> p[i];
	}
 
	MGraph MG(p, n, e);
 
	MG.Dijkstra();
 
	return 0;
}

到了這里，關(guān)于使用鄰接矩陣實(shí)現(xiàn)有向圖最短路徑Dijkstra算法 題目編號(hào):1136的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！