算法模板
const int edge=7; //edge為邊長(zhǎng)
const int INF=100000000; //無窮大碍遍，表示兩點(diǎn)之間無路徑
void Dijkstra(int g[edge][edge],int v,int dist[],int path[]){ //dist存儲(chǔ)最短路徑 path表示最短路徑的上一點(diǎn)
int set[edge]; //記錄數(shù)組
int min,i,j,u;
for(i=0;i<edge;i++){ // 初始化
dist[i]=g[v][i];
set[i]=0;
if(g[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
set[v]=1;path[v]=-1;
for(i=0;i<edge-1;i++){ // 開始尋找最短路徑 時(shí)間復(fù)雜度O(n2)
min=INF;
for(j=0;j<edge;j++){
if(set[j]==0&&dist[j]<min){
u=j;
min=dist[j];
}
}
set[u]=1;
for(j=0;j<edge;j++){
if(set[j]==0&&dist[u]+g[u][j]<dist[j]){
dist[j]=dist[u]+g[u][j];
path[j]=u;
}
}
}
}
輸出最短路徑依次經(jīng)過的點(diǎn)需要借助棧，最短路徑保存在dist[]中靶擦，直接取就行了
const int maxSize=100000;
void printPath(int path[],int a){
int stack[maxSize],top=-1; //借助棧
while(path[a]!=-1){
stack[++top]=a;
a=path[a];
}
stack[++top]=a;
while(top!=-1)
cout << stack[top--] << " ";
}
