基于Dijsktra算法的最短路径求解
描述
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。
输入
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。
输出
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。
输入样例 1
3 3
A B C
A B 1
B C 1
A C 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
E D 20
E F 60
D F 10
A F
0 0
输出样例 1
2
A B C
60
A E D F
#include<iostream>
#include<string>
#include<cstring>
#define MaxInt 32767
#define MVNum 100//最大顶点数
/* 注意是有向图，用邻接矩阵
*/
int D[MVNum];//起点开始到各个点的距离
int S[MVNum];//是否访问过
int Path[MVNum];
using namespace std;
typedef struct
{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum, arcnum;
}AMGraph;
int Locate(AMGraph &G,char s)//返回编号
{
for (int i = ; i <=G.vexnum; i++)
{
if (G.vexs[i] == s)
return i;
}
}
void Creat(AMGraph &G)
{
for (int i = ; i <= G.vexnum; i++)
{
cin >> G.vexs[i];
}
for(int i=;i<=G.arcnum;i++)
for (int j = ; j <= G.arcnum; j++)
{
G.arcs[i][j] = MaxInt;
}
for (int i = ; i < G.arcnum; i++)
{
char a, b;
int c;
cin >> a >> b >> c;
int h, t;
h = Locate(G, a);
t = Locate(G, b);
G.arcs[h][t] = c;//有向图
}
}
void Dijkstra(AMGraph &G,int v0)
{
int n = G.vexnum;
int v;
for (v = ; v <= n; v++)
{
S[v] = ;
D[v] = G.arcs[v0][v];
if (D[v] <MaxInt)
Path[v] = v0;
else
Path[v] = -;
}
S[v0] = ;
D[v0] = ;
for (int i = ; i < n - ; i++)
{
int min =MaxInt;
int v=;
for (int w = ; w <= n; w++)
{
if (S[w] != && D[w] <=min)
{
v = w;
min = D[w];
}
}
S[v] = ;
for (int w = ; w <= n; w++)
{
if (S[w] != && (D[v] + G.arcs[v][w] < D[w]))
{
D[w] = D[v] + G.arcs[v][w];
Path[w] = v;
}
}
}
}
void Print(AMGraph &G,int s,int e)
{
int r[MVNum];//记录路径的编号
r[] = e;
int i = ;
while (Path[r[i-]]!=-)
{
r[i] = Path[r[i - ]];
i++;
}
for (int j = i - ; j > ; j--)
cout << G.vexs[r[j]] << " ";
cout << G.vexs[r[]] << endl;
}
int main()
{
int n, m;
while (cin >> n >> m)
{
if (n == && m == )
break;
AMGraph G;
G.vexnum = n;
G.arcnum = m;
Creat(G);
char start, end;
cin >> start >> end;
int s, e;
s = Locate(G, start);
e = Locate(G, end);
Dijkstra(G, s);
cout <<D[e]<<endl;
Print(G,s,e);
}
return ;
}