A. dijkstra算法如何输出路径
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
#define INFINITE 1000
typedef struct graph
{
int nodenum;
int edgenum;
int matrix[MAX_LEN][MAX_LEN];
}Graph;
typedef struct stack
{
int bottom;
int top;
int printout[MAX_LEN];
}mstack;
int in[MAX_LEN];
int Len[MAX_LEN];
int path[MAX_LEN];
void InitStack(mstack *s)
{
s->bottom=0;
s->top=0;
memset(s->printout,0,sizeof(int)*MAX_LEN);
}
void push(mstack *s,int m)
{
s->printout[s->top++]=m;
}
int pop(mstack *s)
{
return s->printout[--s->top];
}
void InitGraph(Graph *g,int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)g->matrix[i][j]=0;
else g->matrix[i][j]=INFINITE;
}
for(i=1;i<=n;i++)
{
in[i]=0;
Len[i]=INFINITE;
path[i]=0;
}
}
int main()
{
int n,m,i,A,B,templen,count,min,tempmin,si,temp;
while(scanf("%d %d",&n,&m))
{
count=0;
Graph mGraph;
mGraph.edgenum=m;
mGraph.nodenum=n;
InitGraph(&mGraph,n);
for(i=0;i<m;i++)
{
scanf("%d %d %d",&A,&B,&templen);
mGraph.matrix[A][B]=templen;
}
in[1]=1;
path[1]=1; //sava path
Len[1]=0;
for(i=2;i<=n;i++)
{
Len[i]=mGraph.matrix[1][i]; //Init the len
if(Len[i]!=INFINITE)path[i]=1;
}
min=0;
si=1;
while(count<n-1)
{
tempmin=INFINITE;
for(i=1;i<=n;i++)
{
if(in[i]==0&&Len[i]<tempmin) //find the smallest one
{
tempmin=Len[i];
si=i;
}
}
in[si]=1;
for(i=1;i<=n;i++) //updata the length
{
if(in[i]==0&&(tempmin+mGraph.matrix[si][i])<Len[i])
{
Len[i]=tempmin+mGraph.matrix[si][i];
path[i]=si;
}
}
count++;
}
mstack s;
for(i=1;i<=n;i++)
{
temp=i;
InitStack(&s);
if(path[temp]==0)
{
printf("no path\n");
continue;
}
while(path[temp]!=1)
{
push(&s,path[temp]);
temp=path[temp];
}
printf("1-->");
while(s.bottom!=s.top)
{
printf("%d-->",pop(&s));
}
printf("%d min length is %d\n",i,Len[i]);
}
}
return 0;
}
B. 写程序，用算法找迷宫的路径（随意路径或者最短路径）
C. dijkstra算法怎么记录路径
加一个数组pre[]，在更新最短路的时候记录是从哪个点更新过来的，即最短路径的前一个点
求完最短路之后再从终点沿着路径走回去，就可以得到最短的路径了
D. 什么是路径搜索算法
举个例子你大概就明白了，假设从上海东方明珠电视塔到北京天安门有N条线路，可以上海-天津-北京，上海-南京-北京，上海-广州-西藏-北京等等等，选择一条需要的线路这就是路径搜索，用来实现该选择的算法是路径搜索算法，可以选择最短路径，关键路径，如果有费用（权值）就可以选择最便宜路径（权最小），如果有路径需用时（飞机、火车，有些地方只有单一交通工具）就可以选择时间最短路径
用于计算机中的路径搜索就比较广泛了，但大体就是根据上述情况变化来得
E. 蚁群算法 路径
哥们，你这问题还是问得不清不楚的。
F. A*算法用于路径规划，有什么缺点
缺点：A*算法通过比较当前路径栅格的8个邻居的启发式函数值F来逐步确定下一个路径栅格，当存在多个最小值时A*算法不能保证搜索的路径最优。
A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。A*[1] （A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
G. 求一个最优路径算法的思路
同意楼上，最长路径是NPC问题，不存在多项式算法。
证明是简单的：
1、最长无环路问题的判定版本是“给定有向图D和整数k，问D中是否存在长度大于或等于k的无环路”（这一表述对有权图和无权图都有效）。
2、将Hamilton路问题规约到最长无环路问题（的判定版本）是显然的：输入一个n顶点的有向图D，直接问：有向图D中是否存在长度大于等于n-1的无环路？
简言之，对任意n顶点的有向图D，假如能够D中的找到最长无环路P，那么就能立即知道D中是否存在Hamilton路（只需看P的长度是否为n-1即可），从而最长无环路问题是NPC。
小规模就直接DFS吧。大规模的时候DFS剪枝。不过确实不好做呀。
有向无圈图的话可以用dijstra贪心，或者简单用folyed算法就可以了（把最小化变为最大化）。
有圈的话您……或者能缩圈么？可以考虑。总之比较复杂。
H. A*算法找到的路径怎么用坐标显化
A*生成了从初始到结束的连续状态，给下位机发送每个状态的命令，比如是从初始状态开始，往左50，往前20，等等，不断执行每个状态，最终肯定就是到达目的地。
I. 关键路径算法的时间复杂度
所谓关键路径，就是从工程开始到工程结束所用时间最长的路径。这是因为，在途中的每一个阶段开始之前，都要保证此前的准备工作都已完成，要不然后续工程会无法完成，在寻找路径时，只能一条路径一条路径的比较。本题结果是
J. C++ 算法，路径，多谢
仅供参考 了
#include "stdio.h"
#define maxver 10
#define maxright 100
int G[maxver][maxver],record=0,touched[maxver][maxver];
int circle=0;
int FindCircle(int,int,int,int);
int main()
{
int path[maxver][2],used[maxver][maxver];
int i=0,j=0,k=0,t,min=maxright,exsit=0;
int v1,v2,num,temp,status=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if (num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for (j=0;j<num;j++)
for (k=0;k<num;k++)
{
if (j==k)
{
G[j][k]=maxright;
used[j][k]=1;
touched[j][k]=0;
}
else
if (j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if (temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if (temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
used[j][k]=used[k][j]=0;
touched[j][k]=touched[k][j]=0;
}
}
for (j=0;j<num;j++)
{
path[j][0]=0;
path[j][1]=0;
}
for (j=0;j<num;j++)
{
status=0;
for (k=0;k<num;k++)
if (G[j][k]<maxright)
{
status=1;
break;
}
if (status==0)
break;
}
for (i=0;i<num-1&&status;i++)
{
for (j=0;j<num;j++)
for (k=0;k<num;k++)
if (G[j][k]<min&&!used[j][k])
{
v1=j;
v2=k;
min=G[j][k];
}
if (!used[v1][v2])
{
used[v1][v2]=1;
used[v2][v1]=1;
touched[v1][v2]=1;
touched[v2][v1]=1;
path[0]=v1;
path[1]=v2;
for (t=0;t<record;t++)
FindCircle(path[t][0],path[t][0],num,path[t][0]);
if (circle)
{
/*if a circle exsits,roll back*/
circle=0;
i--;
exsit=0;
touched[v1][v2]=0;
touched[v2][v1]=0;
min=maxright;
}
else
{
record++;
min=maxright;
}
}
}
if (!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{ for (i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[0]+1,path[1]+1);
}
return 1;
}
int FindCircle(int start,int begin,int times,int pre)
{
/* to judge whether a circle is proced*/
int i;
for (i=0;i<times;i++)
if (touched[begin]==1)
{
if (i==start&&pre!=start)
{
circle=1;
return 1;
break;
}
else
if (pre!=i)
FindCircle(start,i,times,begin);
else
continue;
}
return 1;
}