#include<iostream>
using namespace std;
#define max 10
#define maxint 320
typedef struct listtu
{
int edgenum;
int vernum;
char mvex[max];
int matrix[max][max];
};
listtu inital()
{
listtu Q;
Q.edgenum = 0;
Q.vernum = 0;
return Q;
}
int getposition(char ch, listtu Q)
{
for (int i = 0;i<Q.vernum;i++)
{
if (Q.mvex[i] == ch)
{
return i;
}
}
return -1;
}
void create(listtu &Q, char vexs[], int vlen, char edges[][2], int edgelen, int weight[])
{
char c1, c2;
Q.edgenum = edgelen;
Q.vernum = vlen;int p1, p2;
//初始化顶点
for (int i = 0;i<vlen;i++)
{
Q.mvex[i] = vexs[i];
}
//初始化邻接矩阵
for (int i = 0;i < vlen;i++)
{
for (int j = 0;j < vlen;j++)
{
Q.matrix[i][j] = max;
}
}
for (int i = 0;i<edgelen;i++)
{
p1 = getposition(edges[i][0], Q);
p2 = getposition(edges[i][1], Q);
Q.matrix[p1][p2] = 1;
}
}
void print(listtu Q)
{
for (int i = 0;i<Q.vernum;i++)
{
for (int j = 0;j < Q.vernum;j++)
{
cout << Q.matrix[i][j] << " ";
}
cout << endl;
}
}
char readchar()
{
char ch;
do
{
cin >> ch;
} while (!((ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z')));
return ch;
}
void create1(listtu &Q)
{
char c1, c2;int p1, p2;char a;int c3;
cout << "输入顶点数";
cin >> Q.vernum;
cout << "输入边数";
cin >> Q.edgenum;
if (Q.vernum < 1 || Q.edgenum<1 || (Q.edgenum>(Q.vernum*(Q.vernum - 1))))
{
cout << "输入错误:不合法的参数" << endl;
return;
}
for (int i = 0;i<Q.vernum;i++)
{
cout << "vertex(" << i << "):";
Q.mvex[i] = readchar();
}
//初始化邻接矩阵
for (int i = 0;i <Q.vernum;i++)
{
for (int j = 0;j < Q.vernum;j++)
{
Q.matrix[i][j] = maxint;
}
}
for (int i = 0;i<Q.edgenum;i++)
{
cout << "edges(" << i << "):";
c1 = readchar();
c2 = readchar();
p1 = getposition(c1, Q);
p2 = getposition(c2, Q);
cout << "输入权值";
cin >> c3;
Q.matrix[p1][p2] = c3;
}
}
void shortest(listtu &Q, char v0)
{
int path[max][max];
int s[max];
int d[max];
int min;
int p = getposition(v0, Q);
for (int i = 0;i < Q.vernum;i++)
{
s[i] = false;
d[i] = Q.matrix[p][i];
for (int j = 0;j < Q.vernum;j++)
{
path[i][j] = -1;
}
if (d[i] < maxint)
{
path[i][0] = p;
path[i][1] = i;
}
}
s[p] = true;
d[p] = 0;
for (int i = 1;i < Q.vernum;i++)
{
min = maxint;
for (int j = 0;j < Q.vernum;j++)
{
if (!s[j] && d[j]<min)
{
p = j;
min = d[j];
}
}
s[p] = true;
for (int j = 0;j < Q.vernum;j++)
{
if (!s[j] &&(d[p] + Q.matrix[p][j] < d[j]))
{
d[j] = d[p] + Q.matrix[p][j];
for (int k = 0;k < Q.vernum;k++)
{
int a = path[p][k];
path[j][k]=a;
if (path[j][k] == -1)
{
path[j][k] = j;
break;
}
}
}
}
}
for (int i = 0;i < Q.vernum;i++)
{
for (int j = 0;j < Q.vernum;j++)
{
cout << path[i][j] << " ";
}
cout << endl;
}
for (int i = 0;i < Q.vernum;i++)
{
cout << Q.mvex[0] << " " << Q.mvex[i] << " " << d[i];
cout << "最短路径为:";
for (int j = 0;j < Q.vernum;j++)
{
if (path[i][j]>-1)
{
cout << Q.mvex[path[i][j]] << " ";
}
}
cout << endl;
}
}
int main()
{
/*char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
char edges[][2] = {
{ 'A', 'C' },
{ 'A', 'D' },
{ 'A', 'F' },
{ 'B', 'C' },
{ 'C', 'D' },
{ 'E', 'G' },
{ 'F', 'G' } };
int weight[] = { 1,2,3,4,5,6,7,8,9 };
int vlen = sizeof(vexs) / sizeof(vexs[0]);
int elen = sizeof(edges) / sizeof(edges[0]);*/
listtu Q;Q = inital();
//create(Q, vexs, vlen, edges, elen, weight);
create1(Q);
print(Q);
shortest(Q, 'A');
}