一、基本概念
- 最短路径：在非网图中，最短路径是指两顶点之间经历的边数最少的路径；在网图中，最短路径是指两顶点之间经历的边上权值之和最少的路径。
- 源点：路径上的第一个顶点。
- 终点：路径上最后一个顶点。
二、Dijkstra算法（只适用于简单路径，不适合回路）
Dijkstra算法用于求单元点最短路径问题，给定有向网图G=(V,E)和源点v属于V，求v到G中其余各个顶点的最短路径。
①基本思路：
- 将顶点集合V分成两个集合，集合S存放源点v和已经确定最短路径的顶点，另一个集合V-S存放未确定最短路径的顶点。
- 初始化：S只包含源点v，对vi属于V-S，待定路径表为从源点v到vi的有向边。
- 在待定路径表中找到当前最短路径，v…vk，将vk加入S，对vi属于V-S，将路v…vkvi与待定路径表中从源点v到vi的最短路径相比较，去路径长度较小者为当前最短路径。
②存储结构：
- 图的存储结构：邻接矩阵
- 辅助数组dist[n]：元素dist[i]表示当前所找到的从源头v到终点vi的最短路径的长度。(dist[i] = min{dist[i]，dist[k]+edge[k][i])
- 辅助数组path[n]：元素path[i]是一个字符串，表示当前从源点v到终点vi的最短路径。（没有弧则为空串）
void Dijkstra(int v)//从源点v出发
{
int i,k,num,dist[MaxSize];
string path[MaxSize];
for(i = 0 ;i<vertexNum ; i++)//初始化数组dist和path
{
dist[i] = edge[v][i];
if(dist[i]!=100)//假设100为边上权的最大值
path[i] = vertex[v]+vertex[i];//vertex数组存储的是顶点，+为字符串连接操作
else
path[i] = "";//没有边可达，即无穷，则为空串
}
for(num = 1 ; num<vertexNum ; num++)//扫描V-S中的所有顶点
{
k = Min(dist,vertexNum);//在dist数组中（路径列表）找到最小值并返回其下标（注意要越过0值）
cout<<path[k]<<dist[k];
for(i = 0 ; i<vertexNum ; i++)//插入新加入的k顶点，修改dist和path数组
{
if(dist[i]>dist[k]+edge[k][i])
{
dist[i] = dist[k]+edge[k][i];
path[i] = path[k]+vertex[i];//+为字符串连接操作
}
}
dist[k] = 0;//将顶点k加入到集合S中
}
}
Dijkstra算法的时间复杂度为O(n^2)，有两个规律：
- 最短路径是按路长度递增的次序产生的。
- 最短路径上可能经过已产生终点的顶点。
实例：以邻接矩阵为存储结构，实现有向带权图的最短路径算法Dijkstra，完整代码如下：
#include <iostream>
using namespace std;
const int MaxSize = 10; //图中最多顶点个数
int visited[MaxSize]={0};
const int MAX = 1000;
struct element //改进：使用结构体数组代替lowcast数组以及adjvex数组
{
int lowcost, adjvex;
};
int MinEdge(element *e,int vertexNum);
template <class DataType>
class MGraph
{
public:
MGraph(DataType a[ ], int n, int e); //构造函数，建立具有n个顶点e条边的图
~MGraph( ) { } //析构函数为空
void DFSTraverse(int v); //深度优先遍历图
void BFSTraverse(int v); //广度优先遍历图
void Dijkstra(int v);
private:
DataType vertex[MaxSize]; //存放图中顶点的数组
int edge[MaxSize][MaxSize]; //存放图中边的数组
int vertexNum, edgeNum; //图的顶点数和边数
};
template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{
int i, j, k ,x;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++)
vertex[i] = a[i];
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
edge[i][j] = MAX;
for (k = 0; k < edgeNum; k++)
{
cout << "请输入两个边顶点的序号：";
cin >> i >> j; //输入边依附的两个顶点的编号
cout << "请输入边的权值：";
cin >> x;
edge[i][j] = x; //置边的标志为1
edge[j][i] = x; //无向图 边是相通的
}
}
template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
cout << vertex[v];
visited[v] = 1;
for (int j = 0; j < vertexNum; j++)
{
if (edge[v][j] != MAX && visited[j] == 0)DFSTraverse(j); //存在与v相连的j点且j点未被访问过 则进一步遍历j点
}
}
template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
int w, j, Q[MaxSize];
int front = -1, rear = -1;
cout << vertex[v];
visited[v] = 1;
Q[++rear] = v; //v点入队
while (front != rear)
{
w = Q[++front]; //Q出队值 w
for (j = 0; j < vertexNum; j++)//遍历所有可能与w相连的点 若有，则输出、标记、入队
{
if (edge[w][j] != MAX && visited[j] == 0)//存在与w点相连的j点且j点未被访问过 则输出j点值 然后标记j点将j点入队
{
cout << vertex[j];
visited[j] = 1;
Q[++rear] = j;
}
}
}
}
int Min(int dist[],int vertexNum)
{
int min = 100;
for(int i=0 ; i<vertexNum ; i++)
{
if(dist[i]<min)
min = dist[i];
}
return min;
}
template<typename DataType>
void MGraph<DataType>::Dijkstra(int v)//从源点v出发
{
int i,k,num,dist[MaxSize];
string path[MaxSize];
for(i = 0 ;i<vertexNum ; i++)//初始化数组dist和path
{
dist[i] = edge[v][i];
if(dist[i]!=100)//假设100为边上权的最大值
path[i] = vertex[v]+vertex[i];//vertex数组存储的是顶点，+为字符串连接操作
else
path[i] = "";//没有边可达，即无穷，则为空串
}
for(num = 1 ; num<vertexNum ; num++)//扫描V-S中的所有顶点
{
k = Min(dist,vertexNum);//在dist数组中（路径列表）找到最小值并返回其下标（注意要越过0值）
cout<<path[k]<<dist[k];
for(i = 0 ; i<vertexNum ; i++)//插入新加入的k顶点，修改dist和path数组
{
if(dist[i]>dist[k]+edge[k][i])
{
dist[i] = dist[k]+edge[k][i];
path[i] = path[k]+vertex[i];//+为字符串连接操作
}
}
dist[k] = 0;//将顶点k加入到集合S中
}
}
int main( )
{
char ch[]={'A','B','C','D','E'};
MGraph<char> MG(ch, 5, 7);
for (int i=0; i<MaxSize; i++)
visited[i]=0;
cout<<"深度优先遍历序列是：";
MG.DFSTraverse(0);
cout<<endl;
for (int i=0; i<MaxSize; i++)
visited[i]=0;
cout<<"广度优先遍历序列是：";
MG.BFSTraverse(0);
cout<<endl;
cout<<"从顶点"<<ch[0]<<"到各终点的最短路径分别是："<<endl;
MG.Dijkstra(0);
cout<<endl;
system("pause");
}
二、Floyd算法（地铁路线规划）
Floyd算法用于求每一对顶点之间的最短路径问题，给定带权有向图G=（V,E），对任意顶点vi和vj(i不等于j)，求顶点vi到vj的最短路径。
①基本思想：
- 假设从vi到vj是最短路径，然后进行n次试探。
- 比较vi vj和vi vk vj的路径长度，去长度较短者作为vi到vj中间顶点的编号不大于0的最短路径。
②存储结构：
- 图的存储结构：邻接矩阵
- 辅助数组dist[n][n]：存放在迭代过程中求得的最短路径。（dist_-1[i][j] = edge[i][j]；dist_k[i][j] = min{dist_k[i][j]，dist_k[i][k]+dist_k-1[k][j]}）->插入顶点k后更新路径的长度
- 辅助数组path[n][n]：在迭代中存放vi到vj的最短路径，初始为“vi vj”
void Floyd()
{
int i,j,k,dist[MaxSize][MaxSize];
string path[MaxSize][MaxSize];
for(i = 0 ; i<vertexNum ; i++)//初始化矩阵dist和path
{
for(j = 0 ; j<vertexNum ; j++)
{
dist[i][j] = edge[i][j];
if(dist[i][j]!=100)//假设权值最大为100
path[i][j] = vertex[i]+vertex[j];
else
path[i][j] = "";
}
}
for(k = 0 ; k<vertexNum ; k++)//n个顶点进行迭代,n个顶点分别插入到二维矩阵(path)的路径中看是否更新路径
{
for(i = 0 ; i<vertexNum ; i++)//二维矩阵的两层循环
{
for(j = 0 ; j<vertexNum ; j++)
{
if(dist[i][k]+dist[k][j]<dist[i][j])
{
dist[i][j] = dist[i][k]+dist[k][j];
path[i][j] = path[i][k]+paht[k][j];
}
}
}
}
}
n个顶点更新迭代n次，插入顶点k时，插入到除k行k列外的其他路径中才有意义。
实例：医院选址问题（《数据结构》课本P211）
