graph-Dijkstra's shortest-path alogorithm

直接贴代码吧，简明易懂。

后面自己写了测试，输入数据为：

a
b
c
d
e
0 1 4
0 2 2
1 2 3
1 3 2
1 4 3
2 1 1
2 3 4
2 4 5
4 3 1

也就是课本上111的图4.9（上面为原图，下面为结果）

程序的输出结果为：

#include <iostream>
#include <string>
using namespace std;  const int maxVertexNum = 20;
const int INF = 99999;typedef struct dGraph{
// vertexes
string vertex[maxVertexNum];
// edges
int edges[maxVertexNum][maxVertexNum];
int vertexNum;
int edgeNum;
// construct a graph
void set(int n, int e) {
vertexNum = n;
edgeNum = e;
//cout << "input vertex" << endl;
for (int i = 0; i < n; i++)
        cin >> vertex[i];
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n ; j++)
        edges[i][j] = INF;
//cout << "input edge" << endl;
    int weight;
    for (int m = 0; m < e; m++) {
    int i,j;
    cin >> i >> j >> weight;
edges[i][j] = weight;
}
}
// Dijkstra's shortest-path alogorithm
void shortestPathDj(int v) {
bool visited[vertexNum] = {false};
int dist[vertexNum] = {INF};
string path[2 * vertexNum];// initiation
for (int i = 0; i < vertexNum; i++) {
dist[i] = edges[v][i];
if (dist[i] < INF)
    path[i] = vertex[v]+vertex[i];
else
    path[i] = "";
}
dist[v] = 0;
visited[v] = 1;
//
int min;
int i, j, k;
for (j = 1; j < vertexNum; j++) {
min = INF;
// find shortest edge.
for (i = 0; i < vertexNum; i++) {
if (dist[i] < min && visited[i] == false) {
min = dist[i];
k = i;
}
}
visited[k] = true;
cout<<path[k]<<" "<<dist[k]<<endl;
for (i = 0; i < vertexNum; i++) {
if (dist[i] > dist[k] + edges[k][i] && visited[i] == false) {
dist[i] = dist[k] + edges[k][i];
path[i] = path[k] + vertex[i];
}
}
}
}} dGraph;int main() {
freopen("in.txt", "r", stdin);
dGraph G;
G.set(5,9);
G.shortestPathDj(0);
return 0;
}