目录
【问题背景】
【相关知识】
【算法思想】
【算法实现】
【伪代码】
【输入输出】
【代码】
【问题背景】
出门旅游，有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，希望在出发之前知道城市之间的最短路程。
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。
我们想知道指定一个城市（源点）到其余各个城市的最短路程，也叫做“单源最短路径”。
【相关知识】
求带权有向图最短路径问题分为两种情况：求从一个顶点到其他各顶点的最短路径，称之为单源最短路径问题；求每对顶点之间的最短路径，称之为多源最短路径问题。
求单源最短路径算法是由狄克斯特拉（Dijkstra）提出的，称为狄克斯特拉算法，是一个按路径长度递增的顺序逐步产生最短路径的方法。
【算法思想】
给定一个图
G和一个起始顶点即源点v，求v到其他顶点的最短路径长度及最短路径。① 初始时，顶点集
S只包含源点，即S={v0}，顶点v0到自已的距离为0。顶点集T包含除v0外的其他顶点，源点v0到T中顶点i的距离为边上的权（若v0与i有边<v0,i>）或∞（若顶点i不是v0的出边相邻点）。② 从
T中选取一个顶点u，它是源点v0到U中距离最小的一个顶点，然后把顶点u加入S中（该选定的距离就是源点v0到顶点u的最短路径长度）。③ 以顶点
u为新考虑的中间点，修改源点v0到U中各顶点j（j∈T）的距离。重复步骤②和③直到
S包含所有的顶点即T为空。
【算法实现】
设置一个数组
dist[0..n-1]，dist[i]用来保存从源点v0到顶点i的目前最短路径长度。
path[j]保存源点到顶点j的最短路径，实际上为最短路径上的前一个顶点u，即path[j]=u。当求出最短路径后由
path[j]向前推出源点到顶点j的最短路径。举例，有如下有向图，求从
0到其余顶点的最短路径：
下表给出了上述有向网G中从源点
0到其余各顶点的最短路径的求解过程。
最后求出顶点
0到1～6各顶点的最短距离分别为4、5、6、10、9和16。以求顶点
0到顶点4的最短路径为例说明通过path求最短路径的过程：
path[4]=5，path[5]=2，path[2]=1，path[1]=0（源点）， 则顶点0到顶点4的最短路径逆为4、5、2、1、0，则正向最短路径为0→1→2→5→4。
【伪代码】
- 初始化数组dist、path和s；
- while (s中的元素个数<n) 2.1 在dist[n]中求最小值，其下标为k； 2.2 输出dist[j]和path[j]； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中；
根据上面的伪代码用邻接矩阵实现Dijkstra算法。
【输入输出】
第一行输入顶点和边的个数vertexNum和arcNum
第二行输入各个顶点的值，为字符型
下面arcNum行依次输入边的起点编号，终点编号和权值
【测试数据】
请输入顶点个数和边的个数：
5 6请输入顶点的值
A B C D E依次输入边的起点编号，终点编号和权值
0 1 1
0 3 1
0 4 1
2 4 1
3 4 1
3 2 1请输入起始顶点：
A输出从A到各个顶点的最短路径：
从A到B顶点的最短路径长度为：1
从A到B顶点的最短路径为：A->B
从A到C顶点的最短路径长度为：2
从A到C顶点的最短路径为：A->D->C
从A到D顶点的最短路径长度为：1
从A到D顶点的最短路径为：A->D
从A到E顶点的最短路径长度为：1
从A到E顶点的最短路径为：A->E
注意没有路径的情况
请输入顶点个数和边的个数：5 7
请输入顶点的值A B C D E
依次输入边的起点编号，终点编号和权值
0 1 10
0 3 30
0 4 100
1 2 50
2 4 10
3 4 60
3 2 20
请输入起始顶点：B
输出从B到各个顶点的最短路径：
从B到A没有路径.
从B到C顶点的最短路径长度为：50
从B到C顶点的最短路径为：B->C
从B到D没有路径.
从B到E顶点的最短路径长度为：60
从B到E顶点的最短路径为：B->C->E
【代码】
#include<iostream>
#include<algorithm>
#include<string>
#include<limits.h>
using namespace std;
const int MAX_V_NUM = 100;
template <class T>
struct EdgeType
{
T from, to; //边依附的两个顶点
int weight; //边上的权值
};
template <class T>
class EdgeGraph
{
private:
char vertex[MAX_V_NUM] = { 0 }; //存放图顶点的数组
int arc[MAX_V_NUM][MAX_V_NUM] = { INT_MAX };
int vexNum, arcNum; //图的顶点数和边数
int s[MAX_V_NUM] = { 0 }; //存储顶点是否被查找过
int start; //输入的起始顶点下标
public:
EdgeGraph(int vNum, int eNum);
void Dijkstra();
int findMinDist(int* dist); //在dist中查找s[i]为0的最小值元素
int getIndex(char v)
{
for (int i = 0; i < vexNum; i++) {
if (vertex[i] == v) {
return i;
}
}
return -1; // 如果找不到顶点，返回-1
}
void displayPath(int* dist, int* path);
};
template <class T>
EdgeGraph<T>::EdgeGraph(int vNum, int eNum)
{
int u, v, w;
vexNum = vNum;
arcNum = eNum;
//arc初始化
for (int i = 0; i < vexNum; i++)
{
for (int j = 0; j < vexNum; j++)
{
if (i != j)
arc[i][j] = INT_MAX;
else
arc[i][j] = 0;
}
}
cout << "请输入顶点的值";
for (int i = 0; i < vexNum; i++)
{
cin >> vertex[i];
}
cout << "依次输入边的起点编号，终点编号和权值\n";
for (int i = 0; i < arcNum; i++)
{
cin >> u >> v >> w;
arc[u][v] = w;
}
cout << "请输入起始顶点：";
char c;
cin >> c;
start = getIndex(c);
}
//迪杰斯特拉
template <class T>
void EdgeGraph<T>::Dijkstra()
{
int dist[MAX_V_NUM] = { INT_MAX };
int path[MAX_V_NUM] = { -1 };
int num = 0; //记录顶点数
int min;//记录最小值
for (int i = 0; i < vexNum; i++)
{
dist[i] = arc[start][i];
if (dist[i] != INT_MAX)
path[i] = start;
else
path[i] = -1;
}
//s数组的初始化
for (int i = 0; i < vexNum; i++)
{
s[i] = 0;
}
s[start] = 1;//顶点放入集合s。
num = 1;
while (num < vexNum) //当顶点数小于图的顶点数
{
min = findMinDist(dist); //找到最小值
for (int i = 0; i < vexNum; i++)
{ //更新dist和path
if ((s[i] == 0) && (dist[min] + arc[min][i] < dist[i]) && dist[min] != INT_MAX && arc[min][i] != INT_MAX) //找到更短的距离，防止距离为无穷的情况
{
dist[i] = dist[min] + arc[min][i];
path[i] = min;
}
}
s[min] = 1; //将新生成的点加入s
num++;
}
//打印输出起始点到各顶点的最短路径
displayPath(dist, path);
}
//找最小值
template <class T>
int EdgeGraph<T>::findMinDist(int* dist)
{
int min = INT_MAX;
int index = -1;
for (int i = 0; i < vexNum; i++) //在dist数组中没有生成树（s[i]=0）的结点中查找
{
if (s[i] == 0)
{
if (dist[i] < min)
{
min = dist[i];
index = i;
}
}
}
return index;
}
//输出路径
template <class T>
void EdgeGraph<T>::displayPath(int* dist, int* path)
{
char result[MAX_V_NUM] = { 0 };
int k = 0;
cout << "输出从" << vertex[start] << "到各个顶点的最短路径：\n";
for (int i = 0; i < vexNum; i++)
{
if (i != start)
{
if (dist[i] <= 0 || dist[i] == INT_MAX)
{
cout << endl;
cout << "从" << vertex[start] << "到" << vertex[i] << "没有路径." << endl;
}
else
{
cout << endl;
cout << "从" << vertex[start] << "到" << vertex[i] << "顶点的最短路径长度为：" << dist[i] << endl;
cout << "从" << vertex[start] << "到" << vertex[i] << "顶点的最短路径为：" << vertex[start];
int j = i;
while (j != start)
{
result[k++] = vertex[j];
j = path[j];
}
for (int l = k - 1; l >= 0; l--)
{
cout << "->" << result[l];
}
k = 0; //将k归0，进行下一次路径记录
cout << endl;
}
}
}
cout << endl;
}
int main()
{
int vNum, eNum;
cout << "请输入顶点个数和边的个数：";
cin >> vNum >> eNum;
EdgeGraph<char> graph(vNum, eNum);
graph.Dijkstra();
return 0;
}
