?? l7_9.cpp
字號:
//用迪杰斯特拉算法求單源點的最短路徑
#include<iostream.h>
const int max=32767;
const int n=5; //max表示圖中頂點的個數
const int e=9;
struct Graph
{
int arcs [n+1][n+1]; //圖的鄰接矩陣
int dist [n+1] ; //存放從源點到各頂點的最短路徑
int path [n+1] ; //存放在最短路徑上該頂點的前一頂點號
int s[n+1]; //已求得的在最短路徑上的頂點的頂點號
}g;
void shortestpath (const int Vl) //Vl為源點
{for (int i=1;i<=n;i++)
{g.dist[i]=g.arcs[Vl][i];
g.s[i]=0; //已求出最短路徑上的頂點集合初始化
if ((i!=Vl)&&(g.dist[i]<max)) g.path[i]=Vl;
else g.path[i]=0;
}
g.s[Vl]=1; g.dist[Vl]=0;
for (i=1; i<n; i++)
{ int min=max; int u=Vl;
for (int j=1; j<=n;j++) //求最短路徑
if (!g.s[j]&& g.dist[j]<min) {u=j,min=g.dist[j];}
g.s[u]=1; // 將距離值最小的頂點并入集合S中
for(int w=1; w<=n; w++) //修改路徑長度
if ((!g.s[w])&&(g.arcs[u][w]<max) &&(g.dist[u]+g.arcs[u][w]<
g.dist[w])) {g.dist[w]=g.dist[u]+g.arcs[u][w]; g.path[w]=u;}
}
for (i=1;i<=n;i++) //輸出路徑長度及路徑
{if (i!=Vl)
{cout<<"最短距離為:"<<g.dist[i]<<" ";
cout<<"經過的頂點為:"<<i; //輸出終點
int pre=g.path[i];
while (pre!=0)
{cout<<"←"<<pre;
pre=g.path[pre];
}
cout<<endl;
}
}
}
void main( )
{ int i,j,w,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) g.arcs[i][j]=0;
else g.arcs[i][j]=max;
for(k=1;k<=e;k++)
{ cout<<"請輸入一條邊及權值:";
cin>>i>>j>>w;
cout<<endl;
g.arcs[i][j]=w;
}
cout<<"請輸入源點:";
cin>>i;
cout<<endl;
cout<<"從"<<i<<"出發的最短路徑為"<<endl;
shortestpath(i);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -