题目描述
用邻接矩阵存储有向图,实现最短路径Dijkstra算法,图中边的权值为整型,顶点个数少于10个。
部分代码提示:
#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;
}
输入描述
首先输入图中顶点个数和边的条数;
再输入顶点的信息(字符型);
再输入各边及其权值。
输出描述
依次输出从编号为0的顶点开始的从小到大的所有最短路径,每条路径及其长度占一行。
输入样例
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文章来源:https://www.toymoban.com/news/detail-428824.html
输出样例
AD 1
AC 2
AB 6
ADE 8
内存阀值:50240K 耗时阀值:5000MS文章来源地址https://www.toymoban.com/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、顶点表
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;//有方向的不用反复设置相同!!!!掉坑了我淦!
}
}
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?:存入的顶点不需要遍历
{
min = dist[i];
pos = i;
}
}
return pos;
}
void MGraph::Dijkstra()
{
int v = 0;
int i, k, num, dist[MaxSize];//权值表
string path[MaxSize];//路径表
for (i = 0; i < vertexNum; i++)
{
dist[i] = arc[v][i];//v-表示当前顶点,i-表示这个顶点与其他顶点的边的权值(希望屏幕前的你能理解)
if (dist[i] != INF)//如果连通
path[i] = vertex[v] + vertex[i];
else
path[i] = "";
}
dist[0] = 0;
for (num = 1; num < vertexNum; num++)//不知道为什么=1?顶点表已经在集合中了,所以不用遍历
{
k = Min(dist, vertexNum);
cout << path[k] <<' ' << dist[k];
for (i = 0; i < vertexNum; i++)//更新最小权值表
{
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?因为0比其他路径权值和都要小所以无法改变
}
}
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;
}
到了这里,关于使用邻接矩阵实现有向图最短路径Dijkstra算法 题目编号:1136的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!