K短路径算法
算法背景
K 最短路径问题是最短路径问题的扩展和变形。1959 年，霍夫曼(Hoffman) 和帕夫雷(Pavley)在论文中第一次提出k 最短路径问题。 k 最短路径问题通常包括两类：有限制的k 最短路问题和无限制的K 最短路问题。 前者要求最短路径集合不含有回路，而后者对所求得的最短路径集合无限制。
算法简介
Yen's算法是Yen 在1971 年提出的以其名字命名 的Yen 算法。Yen's算法采用了递推法中的偏离路径算法思想，适用于非负权边的有向无环图结构。
算法实例：
调用K条最短路径算法，源C，目的H，K为3。B为偏离路径集合。
1.通过Dijkstra算法计算得到最短路径A^1：C-E-F-H，其中，花费为5，A[1] = C-E-F-H；
2.将A[1]作为迭代路径，进行第一次迭代：
(1)以部分迭代路径(即A[1])C路径中，C点为起点，将C-E路径之间的权值设为无穷大，进行一次Dijkstra，得到路径A^2-1：C-D-F-H，花费为8，将A^2-1路径加入B；
(2)以部分迭代路径(即A[1])C-E路径中，E为起点，将E-F路径之间的权值设为无穷大，进行一次Dijkstra，得到路径A^2-2：C-E-G-H，花费为7，将A^2-2路径加入B；
(3)以部分迭代路径(即A[1])C-E-F路径中，F为起点，将F-H路径之间的权值设为无穷大，进行一次Dijkstra，得到路径A^2-3：C-E-F-G-H，花费为8，将A^2-3路径加入B；
迭代完成，B集合中有三条路径：C-D-F-H，C-E-G-H，C-E-F-G-H；选出花费最小的偏离路径C-E-G-H，A[2] = C-E-G-H，移出B集合。
3.将A[2]作为迭代路径，进行第二次迭代：
(1)以部分迭代路径(即A[2])C路径中，C点为起点，将C-E路径之间的权值设为无穷大，进行一次Dijkstra，得到路径A^3-1：C-D-F-H，但B集合已存在该路径，故不存在偏移路径；
(2)以部分迭代路径(即A[2])C-E路径中，E点为起点，将E-G、E-F路径之间的权值设为无穷大 (注意，这里设置两条路径的权值原因是这两条路径分别存在于A[1]和A[2]中)，进行一次Dijkstra，得到路径A^3-2：C-E-D-F-H，花费为8，将A^3-2加入B；
(3)以部分迭代路径(即A[2])C-E-G路径中，***为起点，将C-H路径之间的权值设为无穷大，不存在偏移路径。
迭代完成，B集合中有三条路径：C-D-F-H，C-E-F-G-H，C-E-D-F-H；由于三条路径花费均为8，则根据最小节点数进行判断，选出偏离路径C-D-F-H，A[3] = C-D-F-H。
此时，选出了三条最短路径，分别是：
A[1] = C-E-F-H
A[2] = C-E-G-H
A[3] = C-D-F-H
头文件
#ifndef _GRAPH_H
#define _GRAPH_H
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
#include<fstream>
#include<sstream>
#include<stack>
using namespace std;
#define MAXNODE 99
#define INFINITY 9999
#define K 10
typedef int VertexType;
typedef int EdgeType;
typedef struct node{
VertexType adjnode;
struct node* next;
EdgeType weight;
}EdgeNode;
typedef struct vnode{
VertexType vertex;
EdgeNode* firstedge;
}VertexNode;
typedef struct MatrixGraph{
VertexType vexs[MAXNODE + 1]; //顶点表
EdgeType edges[MAXNODE + 1][MAXNODE + 1]; //邻接矩阵，可看作边表
}MGraph;
typedef struct Pathstruct{ //用于保存一条路径，里面有每一跳的点和该路径总距离
VertexType node[MAXNODE + 1];
EdgeType distance ;
int hop;
}Path;
typedef VertexNode AdjList[MAXNODE + 1];
class Graph{
public:
Graph(string filename);
~Graph(){};
void FindKpath();
void PrintOut();
void Dijkstra(VertexType);
Path Graph::Dijkstra(VertexType,VertexType);
void DijkstraAll();
void PrintShortestPath(VertexType);
void PrintShortestPathAll(void);
void KShortestPath(VertexType);
private:
MGraph mgraph;
// AdjList adjlist;
EdgeType **dist;
VertexType **pre;
Path **Kpath[K+1]; //存储路径，起点存在node[0].node[i]就是第i跳的点
int e,n; //n是节点数node，e是边数edge
};
#endif源文件
#include "graph.h"
//邻接表方式构建图
Graph::Graph(string filename){
int j,k,w;
ifstream fin(filename,ios::in);
fin>>n;
fin>>e;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
mgraph.edges[i][j] = INFINITY;
}
mgraph.vexs[i] = i;
}
for(int i = 1;i <= e;i++){
fin>>j;
fin>>k;
fin>>w;
mgraph.edges[j][k] = w;
mgraph.edges[k][j] = w;
}
dist = (EdgeType **)malloc(sizeof(EdgeType*) * n);
pre = (VertexType **)malloc(sizeof(VertexType*) * n);
for(int i = 1; i <= K; i++){
Kpath[i] = (Path **)malloc(sizeof(Path) * n);
for(int j = 1; j <= n; j++)
Kpath[i][j] = (Path *)malloc(sizeof(Path) * n);
}
for( int i = 1; i <= n; i++){
dist[i] = (EdgeType *)malloc(sizeof(EdgeType) * n);
pre[i] = (VertexType *)malloc(sizeof(VertexType) *n);
}
}
//求出V点的所有最短路径，结果保存在类的变量Kpath[1][v][i]里面，1表示第一短路径，v、i表示从v到i，
//Kpath结构里，node[i]表示第几跳的点，node[0]是自身，也就是v，另外保存了总跳数和总距离
void Graph::Dijkstra(VertexType v){
bool s[MAXNODE];
for(int i = 1; i <= n; i++){
dist[v][i] = mgraph.edges[v][i];
s[i] = 0;
if(dist[v][i] == INFINITY)
pre[v][i] = 0;
else
pre[v][i] = v;
}
s[v] = 1;
dist[v][v] = 0;
for( int i = 2; i <= n; i++){
VertexType u = v;
EdgeType tmp = INFINITY;
for(int j = 1; j <= n; j++){
if(!s[j] && dist[v][j] < tmp){
tmp = dist[v][j];
u = j;
}
}
s[u] = 1;
for(int j = 1; j <= n; j++){
if(mgraph.edges[u][j] + dist[v][u] < dist[v][j]){
dist[v][j] = mgraph.edges[u][j] + dist[v][u];
pre[v][j] = u;
}
}
}
for(VertexType i = 1; i <= n; i++){
int counthop = 0;
EdgeType length = 0;
VertexType j = i;
while(pre[v][j] != 0){
length += mgraph.edges[j][pre[v][j]];
j = pre[v][j];
counthop++;
}
Kpath[1][v][i].hop = counthop;
Kpath[1][v][i].distance = length;
VertexType m = i;
while(counthop){//处理结果是路径node[1]即为第一跳，根据pre[][]把结果弄出来
Kpath[1][v][i].node[counthop] = m;
m = pre[v][m];
counthop--;
}
Kpath[1][v][i].node[counthop] = v;
}
}
//这个跟上面有很大重复，稍微改了下，接收两个点，返回两点之间的最短路径
Path Graph::Dijkstra(VertexType v,VertexType e){
bool s[MAXNODE];
//Path *tmpath = (Path*)malloc(sizeof(Path) * n);
Path tmpath[MAXNODE];
Path nopath;
nopath.distance = 0;
nopath.hop = 0;
int flag = 0;
for(int i = 1; i <= n; i++){
if(mgraph.edges[v][i] != INFINITY){
flag = 1;
break;
}
}
if(flag == 0)
return nopath;
for(int i = 1; i <= n; i++){
dist[v][i] = mgraph.edges[v][i];
s[i] = 0;
if(dist[v][i] == INFINITY)
pre[v][i] = 0;
else
pre[v][i] = v;
}
s[v] = 1;
dist[v][v] = 0;
for( int i = 2; i <= n; i++){
VertexType u = v;
EdgeType tmp = INFINITY;
for(int j = 1; j <= n; j++){
if(!s[j] && dist[v][j] < tmp){
tmp = dist[v][j];
u = j;
}
}
s[u] = 1;
for(int j = 1; j <= n; j++){
if(mgraph.edges[u][j] + dist[v][u] < dist[v][j]){
dist[v][j] = mgraph.edges[u][j] + dist[v][u];
pre[v][j] = u;
}
}
}
for(VertexType i = 1; i <= e; i++){
int counthop = 0;
EdgeType length = 0;
VertexType j = i;
while(pre[v][j] != 0){
length += mgraph.edges[j][pre[v][j]];
j = pre[v][j];
counthop++;
}
tmpath[i].hop = counthop;
tmpath[i].distance = length;
VertexType m = i;
while(counthop){ //处理结果是路径node[1]即为第一跳，不存取本节点
tmpath[i].node[counthop] = m;
m = pre[v][m];
counthop--;
}
tmpath[i].node[counthop] = v;
}
Path tmpath2 = tmpath[e];
return tmpath2;
}
void Graph::PrintShortestPath(VertexType v){
for(VertexType i = 1; i <= n; i++){
int counthop = Kpath[1][v][i].hop;
cout<<v;
for(int j = 1; j <= counthop; j++)
cout<<"-->"<<Kpath[1][v][i].node[j];
cout<<"\nhop: "<<counthop<<endl;
cout<<"distance: "<<Kpath[1][v][i].distance<<endl;
cout<<endl;
}
}
//求出所有点之间的最短路径
void Graph::DijkstraAll(){
for(VertexType i = 1; i <= n; i++){
Dijkstra(i);
}
}
void Graph::PrintShortestPathAll(){
for(VertexType i = 1; i <= n; i++){
PrintShortestPath(i);
cout<<"\n"<<endl;
}
}
void Graph::PrintOut(void){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(mgraph.edges[i][j] != INFINITY && mgraph.edges[i][j] != 0)
cout<<"<"<<i<<","<<j<<">:"<<mgraph.edges[i][j]<<endl;
}
}
cout<<"Output End"<<endl;
}
void Graph::KShortestPath(VertexType v){ //求出v点到其他所有点的K最短路径,K在define里指定
typedef struct tmpedge{
VertexType a,b;
EdgeType c;
}tmpedge;
//vector<Path> pathset;
VertexType end = 8;
Path sufpath;
Path pathset[100];
int pathcount = 0;
stack<tmpedge> tmpstore;
tmpedge t;
for(int j = 1; j <= K - 1; j++){ //第K短路径要参考第K-1短的路径情况
for(int i = 1; i <= Kpath[j][v][end].hop; i++){
int flag = 0;
t.a = Kpath[j][v][end].node[i - 1];
t.b = Kpath[j][v][end].node[i];
t.c = mgraph.edges[Kpath[j][v][end].node[i]][Kpath[j][v][end].node[i - 1]];
tmpstore.push(t);
mgraph.edges[Kpath[j][v][end].node[i - 1]][Kpath[j][v][end].node[i]] = INFINITY;
mgraph.edges[Kpath[j][v][end].node[i]][Kpath[j][v][end].node[i - 1]] = INFINITY; //遍历，另K-1短路径里面的每条边断一次
sufpath = Dijkstra(Kpath[j][v][end].node[i - 1],end); //求出新的路径
if(sufpath.distance == 0 && sufpath.hop == 0){ //如果路径不存在，就把原来设置为无穷的给复原
while(!tmpstore.empty()){
t = tmpstore.top();
tmpstore.pop();
mgraph.edges[t.a][t.b] = t.c;
mgraph.edges[t.b][t.a] = t.c;
}
continue;
}
while(flag != 1){ //flag=1说明新的路径没有与之前的任何K-1条路径的前i个点重合
for(int m = 1;m <= j; m++){ // m <= k - 1
int flag2 = 0;
int count = 1;
for( count = 1; count <= i - 1; count++){ //flag2 = 1 表示前i-1个点不重合
if( Kpath[m][v][end].node[count] != Kpath[j][v][end].node[count])
flag2 = 1;
}
if( flag2 == 0 && Kpath[m][v][end].node[count] == sufpath.node[1]) //flag2 = 0表示前i-1个点重合。
flag2 = 2;
if( flag2 == 2 ){ //flag2 = 2表示前i个点都重合
flag = 0;
t.a = Kpath[m][v][end].node[i - 1];
t.b = Kpath[m][v][end].node[i];
t.c = mgraph.edges[Kpath[m][v][end].node[i]][Kpath[m][v][end].node[i - 1]]; //重合就要把边设为无穷，再求最短路径
tmpstore.push(t);
mgraph.edges[Kpath[m][v][end].node[i - 1]][Kpath[m][v][end].node[i]] = INFINITY;
mgraph.edges[Kpath[m][v][end].node[i]][Kpath[m][v][end].node[i - 1]] = INFINITY;
sufpath = Dijkstra(Kpath[m][v][end].node[i - 1],end);
break;
}
else if( m == j )
flag = 1;
}
}
if(sufpath.distance == 0 && sufpath.hop == 0){ //如果总是重合，这个情况算是结束，复原边的情况。
while(!tmpstore.empty()){
t = tmpstore.top();
tmpstore.pop();
mgraph.edges[t.a][t.b] = t.c;
mgraph.edges[t.b][t.a] = t.c;
}
continue;
}
for(int h = sufpath.hop + i; h >= 1; h--){ //从i遍历出的路径是由两部分组成的，i之前是第K-1短路径的前i个点。后面是新求的。
if (h >= i)
sufpath.node[h] = sufpath.node[h - i + 1];
else{
sufpath.node[h] = Kpath[j][v][end].node[h];
sufpath.hop++;
sufpath.distance += mgraph.edges[Kpath[j][v][end].node[h]][Kpath[j][v][end].node[h - 1]];
}
}
sufpath.node[0] = v;
while(!tmpstore.empty()){
t = tmpstore.top();
tmpstore.pop();
mgraph.edges[t.a][t.b] = t.c;
mgraph.edges[t.b][t.a] = t.c;
}
// pathset.push_back(sufpath);
VertexType noloop[MAXNODE+1] = {0}; //监测路径中是否有环路
int loop = 0;
for(int f = 0; f <= sufpath.hop; f++){
if( noloop[sufpath.node[f]] == 0)
noloop[sufpath.node[f]] = 1;
else
loop = 1;
}
if(loop == 0)
pathset[pathcount++] = sufpath; //没有环路，则放入pathset中，pathset里面放了每一次求出的符合条件的路径
}
int toremove = 0;
Path spath = pathset[0];
if( pathcount == 0){
cout<<"\nno loopless path left\n"<<endl;
cout<<"at most " << j <<" shortest paths are found"<<endl;
break;
}
for(int i = 1; i < pathcount; i++)
if(pathset[i].distance < spath.distance){ //在求K短时候，就是在每一次遍历后，从pathset里面选出一条。
spath = pathset[i]; //注意K短一定要遍历K-1的所有边，但最后的结果可能不是从K-1的遍历中出来的，只要是最短就行
toremove = i;
}
for(int i = 0; i <= pathcount; i++){
if(i >= toremove ){ //pathset输出一条，就把那条删除掉
pathset[i] = pathset[i+1];
}
}
pathcount--;
Kpath[j + 1][v][end] = spath;
int counthop = Kpath[j + 1][v][end].hop;
cout<<v<<"'s "<<j+1<<" shortest path"<<endl;
cout<<v;
for(int l = 1; l <= counthop; l++)
cout<<"-->"<<Kpath[j + 1][v][end].node[l];
cout<<"\nhop: "<<counthop<<endl;
cout<<"distance: "<<Kpath[j + 1][v][end].distance<<endl;
cout<<endl;
}
}
主函数
#include"graph.h"
int main(){
Graph g("graph.txt");
g.PrintOut();
g.DijkstraAll();
g.PrintShortestPathAll();
g.KShortestPath(2);
system("pause");
return 0;
}测试文件
8 11
1 2 4
1 3 5
1 4 7
2 5 5
3 4 4
3 5 6
3 6 7
4 6 4
5 8 6
6 7 5
7 8 2
京公网安备 11010502036488号