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;
}