用邻接矩阵存储有向图，实现最短路径Dijkstra算法，图中边的权值为整型，顶点个数少于10个。
部分代码提示：
#include <iostream>
#include <string>
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输出样例
AD 1
AC 2
AB 6
ADE 8完整代码
#include <iostream>
#include <string>
using namespace std;
const int MaxSize = 10;
const int INF = 32767;
class MGraph
{
public:
MGraph(char a[], int n, int e);
void Dijkstra();
private:
string vertex[MaxSize];
int arc[MaxSize][MaxSize],dist[MaxSize],S[MaxSize];
int vertexNum, arcNum,num;
string path[MaxSize];
};
MGraph::MGraph(char a[], int n, int e)
{
//write your code.
int lowcost,j,i;
vertexNum=n;
arcNum=e;
for(int i=0;i<n;i++)vertex[i]=a[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++){
//if(i==j)arc[i][j]=0;
arc[i][j]=INF;//默认最大
}
}
for(int k=0;k<e;k++)
{
// cout<<k<<":"<<"输入i,j吧"<<endl;
cin>>i>>j>>lowcost;
arc[i][j]=lowcost;
}
} //write your code.
int Min(int dist[], int vertexNum)
{
//write your code.
int k=MaxSize;
for(int i=0;i<vertexNum;i++){
if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;
//cout<<i<<":"<<k<<endl;
}
return k;
}
void MGraph::Dijkstra()
{
//write your code.
for(int i=0;i<vertexNum;i++) {
dist[i] = arc[0][i];//源点到各顶点第一行赋值
if (dist[i] != INF){path[i] = vertex[0] + vertex[i];}
else path[i] = "";//dist数组表示的是顶点到vi的最短路径所以它是一个字符串数组
}
S[0]=0;//令vertex[0]为第一个集合s中的顶点，初始化集合S，S中装的是已经找到最短路径的顶点，初始状态就是只包含源点（0）
dist[0]=0;//标记顶点vetex[0]为源点
dist[MaxSize]=INF;
num=1;
// cout<<"ok";
// for(int i=0;i<vertexNum;i++){
// cout<<dist[i];
// }
//cout<<endl;
while(num<vertexNum){
int k;
//for(int i=0;i<vertexNum;i++){
// cout<<dist[i];}
// for(int i=0;i<vertexNum;i++){
// cout<<path[i];}
//cout<<endl;
// cout<<"pk:"<<k<<endl;
k= Min(dist,vertexNum);
// cout<<k<<endl;
cout<<path[k]<<" "<<dist[k];
//cout<<"pk1";
S[num++]=k;
for(int 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;
}
}
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.DdPrint();
MG.Dijkstra();
return 0;
}
文章评论