vc环境 最短路径算法
发布网友
发布时间：2022-05-30 18:56
共3个回答
热心网友
时间：2023-10-31 23:21
转自:http://space.flash8.net/space/html/07/14107_itemid_400760.html
算法介绍
Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。
举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
Dijkstra 算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。 (u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径 上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。 初始时，源点s的路径长度值被赋为0（d[s]=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有 顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路 径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行 到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步 都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。
伪码
在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。
function Dijkstra(G, w, s)
// 初始化
for each vertex v in V[G] {
d[v] := infinity
previous[v] := undefined
d[s] := 0
}
S := empty set
Q := set of all vertices
while Q is not an empty set { // Dijstra算法主体
u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[v] > d[u] + w(u,v) // 拓展边(u,v)
d[v] := d[u] + w(u,v)
previous[v] := u
}
如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。
现在我们可以通过迭代来回溯出s到t的最短路径
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]
现在序列S就是从s到t的最短路径的顶点集.
时间复杂度
我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
对 于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点 (Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。
相关问题和算法
在Dijkstra 算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删 去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图 的一系列次短路径。
OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无*的降低总花费）。
与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。
如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法 ，以减小最短路径的搜索范围。
另外，用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
A*算法
SPFA算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法
所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。
热心网友
时间：2023-10-31 23:21
#include<iostream>
#include<string>
using namespace std;
#define max_vertex 7 //max_vertex 为实际城市数加一
void shortest(int cost[max_vertex][max_vertex],int dijkstra[max_vertex],int path[max_vertex],int visited[],int start,int end)
{
//cost[][]记录权值(不邻接的两点权值为32767)，dijikstra[]记录最短路径，path[]标记路径
int visited_number,vertex,temp;
for(vertex=1;vertex<max_vertex;vertex++)//初始化数组
{
dijkstra[vertex]=cost[start][vertex];
if(cost[start][vertex]<32767)
path[vertex]=start;
}
for(vertex=1;vertex<max_vertex;vertex++)
visited[vertex]=0;
visited[start]=1;
visited_number=1;
int i;
while(visited_number<max_vertex-1)
{
temp=32767;
i=start;
for(vertex=1;vertex<max_vertex;vertex++)//找到最小的dijkstra[];
if(visited[vertex]==0&&dijkstra[vertex]<temp)
{
i=vertex;
temp=dijkstra[vertex];
}
visited[i]=1;//标记为已访问
visited_number++;
for(vertex=1;vertex<max_vertex;vertex++)//调整非visited[]集合中的最短路径值
if(visited[vertex]==0&&dijkstra[i]+cost[i][vertex]<dijkstra[vertex])
{
dijkstra[vertex]=dijkstra[i]+cost[i][vertex];
path[vertex]=i;
}
// visited_number++;
}
}
//最短路径输出函数
void print_path(string city[],int dijkstra[max_vertex],int path[max_vertex],int visited[max_vertex],int start,int end)
{
int k;
if(visited[end]==1)
{
k=end;
while(k!=start)
{
cout<<city[k]<<" <- ";
k=path[k];
}
cout<<city[k]<<endl;
// cout<<"最短路径值为"<<dijkstra[end]<<endl;
}
else
cout<<start<<"->"<<end<<" "<<"无法到达!"<<endl;
}
//输出函数结束
//-----------------
//函数实现第k条路径节点的存储
void store_node(int dijkstra[max_vertex],int path[max_vertex],int visited[max_vertex],int start,int end,int& node_number,int store[])
{
int k;
node_number=1;
if(visited[end]==1)
{
k=end;
while(k!=start)
{
store[node_number]=k;
k=path[k];
node_number++;
}
store[node_number]=k;
// cout<<"最短路径值为"<<dijkstra[end]<<endl;
}
else
store[node_number]=0;
}
//函数结束-------------
//以下代码实现分块查找
struct indexterm
{
string key;
int low,high;
};
struct indexterm index[3];//以二十六个字母为索引
int search(string temp,string *city,indexterm *index,string whole_name)
{
for(int i=index[*temp.c_str()-97].low;i<=index[*temp.c_str()-97].high;i++)
{
if(city[i]==whole_name)//如果找到，返回在数组中的位置
return i;
}
return 0;
}
//分块查找结束-----
//以下代码实现初始化dijkstra[max_vertex],path[max_vertex],visited[max_vertex]数组
//--------------------------------
int main()
{
int cost[max_vertex][max_vertex]={ {32767, 32767,32767,32767,32767,32767,32767},
{32767,32767, 1,32767, 4,32767,32767},
{32767,32767,32767, 1,2, 32767,3},
{32767,32767,32767,32767,32767,32767, 1},
{32767,32767, 32767,32767,32767, 2,32767},
{32767,32767,32767, 32767,32767,32767,1},
{32767,32767,32767,32767,32767,32767,32767}};
int dijkstra[max_vertex],path[max_vertex],visited[max_vertex];
string start_city,end_city,temp_start,temp_end;
int dijkstra_node_least[max_vertex],path_node_least[max_vertex],visited_node_least[max_vertex];//为求节点最少的路线准备
string city[max_vertex]={"a","anhui","anhua","anqing","beijing","xue","changchun",};//城市数组
//string city[max_vertex]={"a","anqing","anhua","anfu","beijing","beijiang","cuntou",};//城市数组
index[0].low=1;
index[0].high=3;
index[1].low=4;
index[1].high=5;
index[2].low=6;
index[2].high=6;
//String city[80]={"aa","ab","ac","bc","bd","be","bg","cd","ce","db","dc","df","dg","eh","ei","e15","fg","fb","ge","gh","gi","gk","gl","hm","hn","ho","hp","hq","ir","it","iu","jv","jw","jz","jd","jb","kh","kq","kp","kw","lx","ls","mh","mo","ma","nx","nz","ng","nm","om","oh","od","ov","pc","qy","qr","qi","rp","ro","rw","rq","st","su","sw","sz","th","tp","ub","us","ut","uq","vc","vm","wz","wo","xz","xj","xl","ys","ze"}
int best;
int i;
int j;
cout<<"*******1、航班路线自主选择程序 "<<endl;
cout<<"*******2、该测试程序基于deletion algeorithm的ksp（k shortest path）算法"<<endl;
cout<<"*******3、可以给出两点之间前K小最短路径"<<endl;
cout<<"*******4、本程序可以实现自助式查找最优路径以及n个备选最优方案"<<endl;
cout<<"*******5、您还可以要求两点之间必须经过任意多的点"<<endl;
cout<<"*******6、程序会寻找符合您要求的路径，输出最佳，并根据您的需要有任意多种备选方案"<<endl;
cout<<"*******7、按权值大小，自动给出前K条路径"<<endl;
cout<<"*********************************************************************"<<endl;
cout<<endl;
cout<<" 接着，利用广度优先搜索"<<endl;
cout<<" 搜索节点最少的路径,以及第二少，第三少，第四少.....的路径 "<<endl;
cout<<" 当然这些路径的耗费（权值）一定在您的可承受(希望)的范围以内"<<endl;
cout<<"*********************************************************************"<<endl;
cout<<"目的地为 anhui ,anhua,anqing,beijing,xue 之一"<<endl;
cout<<"请输入你的出发地"<<endl;
cin>>start_city;
i=1;
while(start_city!=city[i])
{
i++;
if(i>5)
{
cout<<"出发地有误!请重新输入"<<endl;
i=1;
cin>>start_city;
}
}
cout<<"出发地正确!"<<endl;
cout<<"目的地为 anhui ,anhua,anqing,beijing,xue changchun 之一"<<endl;
cout<<"请输入您的目的地"<<endl;
i=1;
cin>>end_city;
while(end_city!=city[i])
{
i++;
if(i>6)
{
cout<<"目的地有误!请重新输入"<<endl;
i=1;
cin>>end_city;
}
}
i=1;
temp_start=start_city.substr(0,1); //取第一个字符串,准备分块查找
temp_end=end_city.substr(0,1);
//初始化索引表
char str='a';
for(int n=0;n<3;n++)
{
index[n].key=str;
str++;
}
//-------------
int start_position,end_position;//查找起始和终点城市的编号
start_position=search(temp_start,city,index,start_city); //start_position为城市在数组中的下标
//cout<<temp_start<<" "<<temp_end<<endl;
// cout<<"start_position "<<start_position<<endl;
end_position=search(temp_end,city,index,end_city);
// cout<<"end_position "<<end_position<<endl;
shortest(cost,dijkstra,path,visited,start_position,end_position);//找最短路径
//cout<<"start_position "<<start_position<<endl;
int dijkstra_copy[max_vertex],path_copy[max_vertex],visited_copy[max_vertex];
int cost_copy[max_vertex][max_vertex];
for(i=1;i<max_vertex;i++)
for(j=1;j<max_vertex;j++)
{
cost_copy[i][j]=cost[i][j];//为求节点最少的路径准备
}
print_path(city,dijkstra,path,visited,start_position,end_position);//将最短路径打印出来
int node_number;
int store[max_vertex];
store_node(dijkstra,path,visited,start_position,end_position,node_number,store);
best=dijkstra[end_position];
cout<<"最短路径的权值为"<<dijkstra[end_position]<<endl;
cout<<"中转站的数目为"<<node_number-2<<"个"<<endl;
//以下代码实现前k条最短路径的查找与输出
int need_number;
//此k条最短路径算法是通过删除算法来做的
int vertex;
int temp;//暂时存放要删除边的权
int first,second;//分别为一条边上前后两个点
int max=32767;
//初始化dijkstra[max_vertex],path[max_vertex],visited[max_vertex]数组为(k-1)th最短路径时的状态
/*for( i=0;i<max_vertex;i++)
{
dijkstra[i]=cost[start_position][i];
if(cost[start][i]<32767)
path[i]=start_position;
visited[i]=0;
}
visited[start_position]=1;*/
int edge_start,edge_end;
int flag=1;
int k;
cout<<"*****************************"<<endl;
//必须经过某城市
cout<<"让我们继续简化您的工作"<<endl;
char ch;
cout<<"您需要中途必经其它城市吗？y or n"<<endl;
cin>>ch;
string mid_node[max_vertex];
int mid_city=1;
string temp_mid;
int mid_position;
int mid_store[max_vertex];
for(k=1;k<max_vertex;k++)
mid_store[k]=max_vertex+1;
if(ch=='y'||ch=='Y')
{
while(ch!='n'&&ch!='N')
{
cout<<"您希望路线必须经过哪些城市？"<<endl;
cout<<"请输入城市名"<<endl;
cin>>mid_node[mid_city];
temp_mid=mid_node[mid_city].substr(0,1);//
mid_position=search(temp_mid,city,index,mid_node[mid_city]);
mid_store[mid_city]=mid_position;
//cout<<"mid_position "<<mid_position<<endl; for debug
mid_city++;
cout<<"continue? y or n "<<endl;
cin>>ch;
}
}
else
mid_store[0]=end_position;
int same_number=0;
cout<<"请输入您需要多少种备选方案"<<endl;
cin>>need_number;
cout<<endl;
while(need_number>=1)
{
max=32767;
//根据上次删除的边初始化数组
for(vertex=1;vertex<max_vertex;vertex++)//初始化数组
{
dijkstra[vertex]=cost[start_position][vertex];
if(cost[start_position][vertex]<32767)
path[vertex]=start_position;
}
for(vertex=1;vertex<max_vertex;vertex++)
visited[vertex]=0;
visited[start_position]=1;
//记录当前的数组信息
for(i=1;i<max_vertex;i++)
{
path_copy[i]=path[i];
dijkstra_copy[i]=dijkstra[i];
visited_copy[i]=visited[i];
}
//依次删除k-th最短路径上的边
i=1;
j=node_number;
while(i<=j-1)//循环node_number-1次
{
first=store[node_number];
second=store[node_number-1];
temp=cost[first][second];//将边值储存
cost[first][second]=32767;//将边删除
shortest(cost,dijkstra,path,visited,start_position,end_position);
if(dijkstra[end_position]<=max)//删除边后，找到最短的一条路径即为所求
{
max=dijkstra[end_position];
edge_start=first;//记录下删除的边
edge_end=second;
}
//将数组恢复到(k-1)最短路径的状态，准备删除下一条边
for(k=1;k<max_vertex;k++)
{
path[k]=path_copy[k];
dijkstra[k]=dijkstra_copy[k];
visited[k]=visited_copy[k];
}
cost[first][second]=temp;//恢复删除的边
node_number--;//准备删除下一条边
i++;
}
if(max==32767)//没找到最短路径
{
cout<<"对不起，目前为止，最多只能有"<<flag<<"个方案!"<<endl;
break;
}
cost[edge_start][edge_end]=32767;//根据记录的最短路,删除该边
//cout<<"visit here!"<<endl;
shortest(cost,dijkstra,path,visited,start_position,end_position);
//cout<<"visit here!"<<endl;//for debug
store_node(dijkstra,path,visited,start_position,end_position,node_number,store);
same_number=0;
for(j=1;j<max_vertex;j++)
{
for(k=1;k<max_vertex;k++)
if(store[k]==mid_store[j])
same_number++;
}
//cout<<" same_number "<<same_number<<endl;
//cout<<"mid_city-1 "<<mid_city-1<<endl;
if(same_number==mid_city-1)
{
cout<<"**************************************"<<endl;
flag++;
cout<<endl;
cout<<" 第"<<flag<<"条路径的权值为: "<<dijkstra[end_position]<<endl;
cout<<"路径为： "<<endl;
print_path(city,dijkstra,path,visited,start_position,end_position);
cout<<"中转站的数目为 "<<node_number-2<<"个"<<endl;
cout<<"**************************************"<<endl;
need_number--;
}
}
//搜索节点最少的路线
//---------------------------------------
cout<<"继续搜索中转站最少的路线? y or n"<<endl;
cin>>ch;
cout<<endl;
int cost_node_least[max_vertex][max_vertex]={ {32767, 32767,32767,32767,32767,32767,32767},
{32767,32767, 1,32767, 1,32767,32767},
{32767,32767,32767, 1,1, 32767,1},
{32767,32767,32767,32767,32767,32767, 1},
{32767,32767, 32767,32767,32767, 1,32767},
{32767,32767,32767, 32767,32767,32767,1},
{32767,32767,32767,32767,32767,32767,32767}};
int extra;
for(vertex=1;vertex<max_vertex;vertex++)//初始化数组
{
dijkstra_node_least[vertex]=cost_node_least[start_position][vertex];
if(cost_node_least[start_position][vertex]<32767)
path_node_least[vertex]=start_position;
}
for(vertex=1;vertex<max_vertex;vertex++)
visited_node_least[vertex]=0;
visited_node_least[start_position]=1;
flag=1;
int sum_cost=0;
int temp_node_number;
if(ch!='n')
{
shortest(cost_node_least,dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position);//找最短路径
store_node(dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position,node_number,store);
temp_node_number=node_number;
cout<<"中转站最少的方案为: "<<endl;
print_path(city,dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position);
// cout<<"node_number "<<node_number<<endl;
while(temp_node_number>1)
{
sum_cost=sum_cost+cost_copy[store[temp_node_number]][store[temp_node_number-1]];
// cout<<"sum_cost "<<sum_cost<<endl;
temp_node_number--;
}
cout<<"该方案的耗费是： "<<sum_cost<<endl;
cout<<"中转站的数目为: "<<dijkstra_node_least[end_position]-1<<endl;
}
if(ch=='y'||ch=='Y')
{
// cout<<"最小的权值是"<<best<<endl;
cout<<"请输入您最多还能承受多少钱？"<<endl;
cin>>extra;
cout<<endl;
}
sum_cost=0;
//cout<<"start position "<<start_position<<endl;
//cout<<"end position "<<end_position<<endl;
cout<<"请输入你需要的方案数"<<endl;
cin>>need_number;
cout<<endl;
// cout<<"best+extra-- "<<best+extra<<endl;//for beg
while(need_number>=1&&ch!='n')
{
max=32767;
// cout<<"need_number -- "<<need_number<<endl;
//根据上次删除的边初始化数组
for(vertex=1;vertex<max_vertex;vertex++)//初始化数组
{
dijkstra_node_least[vertex]=cost_node_least[start_position][vertex];
if(cost_node_least[start_position][vertex]<32767)
path_node_least[vertex]=start_position;
}
for(vertex=1;vertex<max_vertex;vertex++)
visited_node_least[vertex]=0;
visited_node_least[start_position]=1;
//记录当前的数组信息
for(i=1;i<max_vertex;i++)
{
path_copy[i]=path_node_least[i];
dijkstra_copy[i]=dijkstra_node_least[i];
visited_copy[i]=visited_node_least[i];
}
//依次删除k-th最短路径上的边
i=1;
j=node_number;
while(i<=j-1)//循环node_number-1次
{
first=store[node_number];
second=store[node_number-1];
temp=cost_node_least[first][second];//将边值储存
cost_node_least[first][second]=32767;//将边删除
shortest(cost_node_least,dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position);
//cout<<end_position<<endl;
// cout<<"dijkstra_node_least[end_position]"<<dijkstra_node_least[end_position]<<endl;
if(dijkstra_node_least[end_position]<=max)//删除边后，找到最短的一条路径即为所求
{
max=dijkstra_node_least[end_position];
edge_start=first;//记录下删除的边
edge_end=second;
}
//将数组恢复到(k-1)最短路径的状态，准备删除下一条边
for(k=1;k<max_vertex;k++)
{
path_node_least[k]=path_copy[k];
dijkstra_node_least[k]=dijkstra_copy[k];
visited_node_least[k]=visited_copy[k];
}
cost_node_least[first][second]=temp;//恢复删除的边
node_number--;//准备删除下一条边
i++;
}
// cout<<"max==="<<max<<endl;//for debug
if(max==32767)//没找到最短路径
{
cout<<"对不起，目前为止，最多只能有"<<flag<<"个方案!"<<endl;
break;
}
cost_node_least[edge_start][edge_end]=32767;//根据记录下的最短路删除该边
shortest(cost_node_least,dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position);
//cout<<"visited here!!!"<<endl;
store_node(dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position,node_number,store);
sum_cost=0;
temp_node_number=node_number;
while(temp_node_number>1)
{
sum_cost=sum_cost+cost_copy[store[temp_node_number]][store[temp_node_number-1]];
// cout<<"temp_node_number "<<temp_node_number<<endl;
// cout<<"sum_cost "<<sum_cost<<endl;
temp_node_number--;
}
// cout<<"该方案的耗费是： "<<sum_cost<<endl;
if(sum_cost<=best+extra)
{
flag++;
cout<<endl;
cout<<" 第"<<flag<<"条路径的中转站数目为: "<<dijkstra_node_least[end_position]-1<<endl;
cout<<"路径为： "<<endl;
print_path(city,dijkstra_node_least,path_node_least,visited_node_least,start_position,end_position);
cout<<"该方案的耗费是： "<<sum_cost<<endl;
cout<<"***********************************"<<endl;
need_number--;
}
}
system("PAUSE");
return 0;
}
热心网友
时间：2023-10-31 23:22
