vc环境 最短路径算法
作者&投稿：赵影 （若有异议请与网页底部的电邮联系）
每次更新节点的最短路的时候，记录是由哪个节点更新过来的，求完最短路后，从终端回溯，直到始点
伪代码一下：
void GetMinDistPath()
{
int dist[nVertex]; //各个点到start_point的距离
int father[nVertex]; //记录是哪个节点更新过来的
int g[nVertex][nVertex]; //邻接矩阵存图，没有边记为infinity
bool vis[nVertex]; //是否已经确定最短路
read_graphy();
init_distance_as_infinity();
init_vis_as_false();
dist[start_point] = 0; vis[start_point] = true;
father[start_point] = -1;
for(int i = 1;i < nVertex;i ++) {
int u = get_not_vis_min_dist_point();
vis[u] = true;
for(int j = 0;j < nVertex;j ++)
if(dist[j] > dist[u] + g[u][j]) {
dist[j] = dist[u] + g[u][j];
father[j] = u; //更新father
}
}
//打印最短路径：start_point <--- end_point
for(int u = end_point;u != -1;u = father[u]) printf("%d ",u);
return;
}
d[i][j][k]表示第i列 左边的第j个到右边的第k个的距离（第i个和第k个均表示图中这一列的第i,k个，不是左边第j个指向的第k个），d[2][2][2]就表示B2到C2的距离就是8，d[2][2][4]表示B2到C4为4
望采纳
转自: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的最短路。
这是个求最短路径还有最短K条最短路径的算法 前K条最短路径算法用的是删除算法 直接粘贴到vc里面就可以运行
#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","baixue","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,baixue 之一"<<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,baixue 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 bedug
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;
}
晕,A*寻路算法最块,最好,搜索一下 网上有A*算法的说明和源码的,在GOOGLE搜
斋斌达美： 原发布者:萨sky简述几种常用的最短路径算法摘要:随着社会的发展,最短路径问题在现实生活中占据的地位越来越重要.求解这一类问题的方法有很多,包括Floyd算法、Dijkstra算法、Bellman-Ford算法、动态规划算法和智能优化算法.其...
哈密地区13617483401： 用C或C++实现求最短路径的Dijkstra算法 - ？
斋斌达美： /* 用邻接矩阵表示的图的Dijkstra算法的源程序*/ #include #define MAXVEX 100 typedef char VexType; typedef float AdjType; typedef struct { VexType vexs[MAXVEX]; /* 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ int n; /* 图的...
哈密地区13617483401： 迷宫最短路径(c语言编程) - ？
斋斌达美： 做出来了..花了一天时间..唉..下面是代码.. 如果看的麻烦的话..留个邮箱,我直接把程序文件发过去.. #include<stdio.h> #include<stdlib.h> #include<time.h> int** CreateTwoDimensionalArr(int a, int b)//动态创建二位数组.. { ...
哈密地区13617483401： C#最短路径算法中怎么走? - ？
斋斌达美： 用floyd或者迪杰斯特拉算法 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵. 从图的带权邻接矩阵A=[a(i,j)] n*n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n).矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径. 采用的是松弛技术,对在i和j之间的所有其他点进行一次松弛.所以时间复杂度为O(n^3);
哈密地区13617483401： c语言数据结构 最短路径问题代码 - ？
斋斌达美： 直接看代码:#include <stdlib.h> #define MAXVEX 10 typedef struct graph{int n,e;//顶点数、边数char vexs[MAXVEX];//顶点数组int arcs[MAXVEX][MAXVEX];//邻接矩阵int kind;//类型:0有向图;1无向图;2有向网;3无向网 } MGraph...
哈密地区13617483401： 怎么用c语言实现单源最短路径问题?要求是用Dijkstra算法,最好写出所有的代码 ,包括结构定义等等,对一 - ？
斋斌达美： C语言代码://清华大学出版社光盘的代码 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D) { // 算法7.15// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]// 及其带权长度D[v].// 若P[v][w]为TRUE,则w...
哈密地区13617483401： 数据结构C语言,单源结点最短路径问题 - ？
斋斌达美： #include <stdio.h> #define MAX 100int * dist; int **road;void ShortPaths(int v,int **c,int **r,int n) {int i,j;int *s;s=(int *)malloc(n*sizeof(int));for(i=0;i<n;i++){dist[i]=c[v][i];r[v][i]=v;s[i]=0;}dist[v]=0;s[v]=1;for(i=0;i<=n;i++){int temp=10000;int ...
哈密地区13617483401： 我需要一个在C++上可以运行成功的最短路径算法—Floyd(弗洛伊德)算法 - ？
斋斌达美： 第一行我觉得注释掉之后就能允许用户输入图的情况了.即注释掉freopen(＂input2.txt＂, ＂r＂, stdin);
哈密地区13617483401： 最短路径弗洛德算法怎么理解 - ？
斋斌达美： Dijkstra算法,A*算法和D*算法 Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点...
哈密地区13617483401： 严蔚敏的数据结构(C语言版)最短路径算法 代码段:p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什么意思 - ？
斋斌达美： 我认为是列整体赋值的意思 行代表各个点 一个点一个点的去访问 成功选出了下一个点后 需要知道路径 把当前列复制过去等于告诉 路径了 但是问题是不能直接读出路径的顺序 应该还是需要一个算法去读P矩阵 不过这个算法也简单 就是同行逐次增一就行 我是这么理解的...
