與最小生成樹有些不一樣.在這里提出三種算法.
dijkstra算法,是最普通也是最簡(jiǎn)單的.與prim算法有些類似,但適用范圍又不一樣,有打印路徑和不打印路徑的小分法.注意不能用于權(quán)值有負(fù)的圖!!!(而且可以用優(yōu)先隊(duì)列優(yōu)化,可以查一下模板,也比較簡(jiǎn)單).
首先是不打印路徑的dijkstra,類似于DP.(打印單源路徑,即某一特定點(diǎn)到其他點(diǎn)的距離)
最近發(fā)現(xiàn)一個(gè)坑點(diǎn),初始化地圖時(shí)最好放在輸入前面,然后輸入信息時(shí)要求小于對(duì)應(yīng)地圖的位置時(shí)才存入地圖中,因?yàn)槲覀円蟮氖亲疃搪?必須保證地圖中是兩點(diǎn)的最短距離!!!若之后又輸入了某點(diǎn)的信息后距離是比之前的更長(zhǎng)的則不能替換的,否則求出來(lái)的就不是最短路了.!!!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxp = 2005;
const int INF= 1000000;
int edge[maxp][maxp];
int near[maxp];
int low[maxp];
int n;
void dijkstra(int u)//從u點(diǎn)開始找出距離所有的點(diǎn)最短距離.
{ memset(low,0,sizeof(low));
for(int i=0;i<n;i++)
near[i]=edge[u][i];
low[u]=1;
for(int i=0;i<n;i++){
int minn=INF;
int v=-1;
for(int j=0;j<n;j++){
if(!low[j] && near[j]<minn)
v=j,minn=near[j];
}
low[v]=1;
for(int j=0;j<n;j++)
near[j]=min(near[j],edge[v][j]+near[v]);//這樣寫更簡(jiǎn)單,不用那個(gè)if也行,因?yàn)椴粫?huì)影響原先那個(gè)最短的.
//加那個(gè)if時(shí)間更快點(diǎn)而已,也體現(xiàn)了這個(gè)算法不能使用與權(quán)值有負(fù)的邊.
//如果要打印路徑,則這樣就不行.好好想想
}
for(int i=0;i<n;i++){
printf("%d ",near[i]);
}
printf("\n");
}
int main()//輸入哪里怎么改才好輸入就是自己的事.
{
int i,j;
int u,v,w;
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j) edge[i][j]=0;
else edge[i][j]=INF;
}
}
while(1)
{
scanf("%d %d %d",&u,&v,&w); //讀入邊的起點(diǎn)和終點(diǎn)
if(u==-1 && v==-1 && w==-1) break;
if(w<edge[u][v]) //這樣就可以保證圖中存的是兩點(diǎn)間的最短距離.
edge[u][v]=w; //構(gòu)造鄰接矩陣（這里的輸入也說(shuō)明了它是單向的,既有向）//對(duì)應(yīng)的無(wú)向圖改成雙向的就行了.
}
dijkstra(0);//從0開始到所有點(diǎn)的最短距離.(要求那個(gè)點(diǎn),就傳那個(gè)點(diǎn)進(jìn)去就行了)
/*--------打印臨接矩陣------
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
printf("%6d ",edge[i][j]);
}
printf("\n");
}
--------------------------*/
}
打印路徑的.
#include<cstdio>
#include<cstring>
#define INF 1000000 //無(wú)窮大
#define maxn 20 //頂點(diǎn)個(gè)數(shù)的最大值
int n;//頂點(diǎn)個(gè)數(shù)
int Edge[maxn][maxn];
int s[maxn];
int dist[maxn];
int path[maxn];//因?yàn)橐蛴÷窂?所以需要一個(gè)數(shù)組保存這條邊來(lái)自于那一條邊,這樣回溯輸出便可輸出路徑.
void dijkstra(int v0)//求v0到其他點(diǎn)的最短路徑.
{ int i,j,k;
for(i=0;i<n;i++)
{
dist[i]=Edge[v0][i];
s[i]=0;//初始化s數(shù)組,用于保存找過(guò)的點(diǎn).
if(i!=v0 && dist[i]<INF) path[i]=v0;
else path[i]=-1;
}
s[v0]=1;//頂點(diǎn)v0加入到頂點(diǎn)集合s中.
for(int i=1;i<n;i++)
{ int mini=INF,u=v0;//選擇當(dāng)前集合t中具有最短路徑的頂點(diǎn)u；
for(int j=0;j<n;j++){
if(!s[j] && dist[j] < mini){ //選擇下一次到已知頂點(diǎn)最短的點(diǎn)。
u=j,mini=dist[j];
}
}
s[u]=1;//將頂點(diǎn)u加入到集合s,表示他的最短路徑已求到.
//修改t集合中頂點(diǎn)dist和path數(shù)組元素值.
for(j=0;j<n;j++){
if(!s[j] && dist[u] + Edge[u][j] < dist[j]){ //未被標(biāo)記且比已知的短，可更新
dist[j]=dist[u] + Edge[u][j] ;
path[j]=u;
}
}
}
}
int main()
{
int i,j;//循環(huán)變量.
int u,v,w;//邊的起點(diǎn)與終點(diǎn)及權(quán)值.
scanf("%d",&n);//頂點(diǎn)個(gè)數(shù)
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j) edge[i][j]=0;
else edge[i][j]=INF;
}
}
while(1)
{
scanf("%d %d %d",&u,&v,&w); //讀入邊的起點(diǎn)和終點(diǎn)
if(u==-1 && v==-1 && w==-1) break;
if(w<mapp[u][v]) //這樣就可以保證圖中存的是兩點(diǎn)間的最短距離.
Edge[u][v]=w; //構(gòu)造鄰接矩陣（這里的輸入也說(shuō)明了它是單向的,既有向）//對(duì)應(yīng)的無(wú)向圖改下就行了.
}
dijkstra( 0 );//求頂點(diǎn)0到其他路徑的最短路徑.//求單源路勁最短.
int shortest[maxn];//輸出最短路徑上的各個(gè)頂點(diǎn)時(shí)存放各個(gè)頂點(diǎn)的序號(hào).
for(i=1;i<n;i++){
printf("%d\t",dist[i]);//輸出頂點(diǎn)0到頂點(diǎn)i的最短路徑長(zhǎng)度.
memset(shortest ,0,sizeof(shortest));//path數(shù)組的作用在這里,因?yàn)楹竺嬉敵?所以必須要一個(gè)數(shù)組來(lái)保存路徑.
int k=0;
shortest[k]=i;
/*for(int i=0;i<n;i++){
printf("%d ",path[i]);
}
putchar('\n');*/
while(path[shortest[k]]!=0)//這里的作用就是回溯輸出路徑.不懂就寫出來(lái)看下就可以了.
{
k++;
shortest[k]=path[shortest[k-1]];
}
k++;
shortest[k]=0;
for(j=k;j>0;j--)
printf("%d-->",shortest[j]);
printf("%d\n",shortest[0]);
}
}
第二種 最暴力 的算法,floyd(適用于點(diǎn)數(shù)比較少的情況，允許有權(quán)值為負(fù)的邊)(可以打印任意兩點(diǎn)間的最短距離)(復(fù)雜度飛常高,不是一定要用,則盡量不要用)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e4+5;
const int inf=1e9+7;
int edge[maxn][maxn];//點(diǎn)i到j(luò)的距離.
int n;
void floyd()//可以找到任意兩點(diǎn)的最短距離.
{
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
//暴力每一點(diǎn)到每一點(diǎn)所有的可能性,三重循環(huán)的純暴力方法.
//如果不是很明白,則寫出來(lái)看看就可以了.
//循環(huán)順序不能變,否則會(huì)WA,現(xiàn)在不是太懂,等懂了再來(lái)解釋,現(xiàn)在先記住順序必須是這樣的!
//因?yàn)楸仨氁潭ㄖ虚g那個(gè)點(diǎn), 去枚舉起點(diǎn)和終點(diǎn), 這樣對(duì)于每一條邊都會(huì)去松弛, .
//而交換了順序后是中間那個(gè)點(diǎn)在不斷變換, 所以對(duì)于有些邊更新時(shí)還是初始值之間進(jìn)行更新,這樣就是錯(cuò)的.
}
}
}
}
/*核心思想為開始允許可以從第一個(gè)點(diǎn)中轉(zhuǎn),然后允許才能夠1,2中轉(zhuǎn),到最后1~n中轉(zhuǎn),找到每?jī)蓚€(gè)點(diǎn)之間的最短路.*/
int main()
{
int i,j;//循環(huán)變量.
int u,v,w;//邊的起點(diǎn)與終點(diǎn)及權(quán)值.
scanf("%d",&n);//頂點(diǎn)個(gè)數(shù)
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j) edge[i][j]=0;
else edge[i][j]=INF;
}
}
while(1)
{
scanf("%d %d %d",&u,&v,&w); //讀入邊的起點(diǎn)和終點(diǎn)
if(u==-1 && v==-1 && w==-1) break;
if(w<mapp[u][v]) //這樣就可以保證圖中存的是兩點(diǎn)間的最短距離.
edge[u][v]=w; //構(gòu)造鄰接矩陣（這里的輸入也說(shuō)明了它是單向的,既有向）//對(duì)應(yīng)的無(wú)向圖改下就行了.
}
/*for(i=0;i<n;i++)//打印鄰接矩陣.
{
for(j=0;j<n;j++)
{
printf("%d ",edge[i][j]);
}
printf("\n");
}*/
floyd();
for(int i=0;i<=5;i++){
printf("%d ",edge[1][i]);//打印1到其余點(diǎn)的最短路徑.//可以打印任何點(diǎn)到任一點(diǎn)的距離.
}
printf("\n");
}
第三種,SPFA算法,這個(gè)算法是最好的,也可以適用于權(quán)值有負(fù)的邊,時(shí)間復(fù)雜度也是最低的.(也是可以優(yōu)化的+SLF,可以去網(wǎng)上搜搜模板)(求源點(diǎn)到其余點(diǎn)的最短距離)
(這個(gè)是單純求最短路的,下面還有用這個(gè)算法去求該圖有無(wú)負(fù)環(huán)的)
(判斷負(fù)環(huán)就是對(duì)每一個(gè)入隊(duì)點(diǎn)數(shù)進(jìn)行標(biāo)記,當(dāng)入隊(duì)次數(shù)超過(guò)了一定的范圍是,可以判斷該圖中存在負(fù)環(huán)可以上網(wǎng)搜搜(一般圖中為2次,具體怎么證明的也不是很清楚))
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e6;
const int maxp=1e4+5;
const int eps=1e-6;
const int inf=1e9; //這個(gè)inf必須足夠大,否則會(huì)影響后面的判斷的.(int 不夠 就用 ll )
int cas=1;
int edge[maxp][maxp];
int vis[maxp],dis[maxp];
queue<int>q;
int n,m;
void spfa(int u)
{
CLR(vis);
vis[u]=1;
q.push(u);
dis[u]=0;
while(!q.empty())
{
int tmp=q.front();
q.pop();
vis[tmp]=0;//消除標(biāo)記.
for(int i=1;i<=n;i++){
if(dis[i] > edge[tmp][i]+dis[tmp]){
dis[i]=edge[tmp][i]+dis[tmp];
if(!vis[i]){
vis[i]=1;//進(jìn)行入隊(duì)標(biāo)記.
q.push(i);
}
}
}
}
}
int main()//水題是hdu2544(三種方法都適用)
{
while(~scanf("%d %d",&n,&m)){
if(n==0 && m==0)
break;
for(int i=1;i<=n;i++){
dis[i]=inf;
for(int j=1;j<=n;j++){
if(i==j) edge[i][j]=0;
else edge[i][j]=inf;
}
}
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(w<edge[u][v]) //這樣就可以保證圖中存的是兩點(diǎn)間的最短距離.
edge[u][v]=edge[v][u]=w;
}
/*for(int i=1;i<=n;i++){//打印臨接表出來(lái)看下.
for(int j=1;j<=n;j++){
printf("%d ",edge[i][j]);
}
printf("\n");
}*/
while(!q.empty())
{
q.pop();
}
spfa(1);//從1到其他任何點(diǎn)的最短距離.
printf("%d\n",dis[n]);
}
}
所以題目要是要求求任意兩點(diǎn)間的最短距離,則用floyd算法
spfa算法的棧寫法(其實(shí)跟隊(duì)列是基本一樣的,就是把隊(duì)列的地方改成棧就可以了,就是可能內(nèi)存或運(yùn)行效率有點(diǎn)不同,看下知道有這種寫法就可以了)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stack>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e6;
const int maxp=1e4+5;
const int eps=1e-6;
const int inf=1e9; //這個(gè)inf必須足夠大,否則會(huì)影響后面的判斷的.(int 不夠 就用 ll )
int cas=1;
int edge[maxp][maxp];
int vis[maxp],dis[maxp];
stack<int>s;
int n,m;
void spfa_dfs(int u)
{
CLR(vis);
vis[u]=1;
s.push(u);
dis[u]=0;
while(!s.empty())
{
int tmp=s.top();
s.pop();
vis[tmp]=0;
for(int i=1;i<=n;i++){
if(dis[i] > edge[tmp][i]+dis[tmp]){
dis[i]=edge[tmp][i]+dis[tmp];
if(!vis[i]){
vis[i]=1;
s.push(i);
}
}
}
}
}
int main()//水題是hdu2544(三種方法都適用)
{
while(~scanf("%d %d",&n,&m)){
if(n==0 && m==0)
break;
for(int i=1;i<=n;i++){
dis[i]=inf;
for(int j=1;j<=n;j++){
if(i==j) edge[i][j]=0;
else edge[i][j]=inf;
}
}
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(w<edge[u][v]) //這樣就可以保證圖中存的是兩點(diǎn)間的最短距離.
edge[u][v]=edge[v][u]=w;
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",edge[i][j]);
}
printf("\n");
}*/
while(!s.empty())
s.pop();
spfa_dfs(1);//從1到其他任何點(diǎn)的最短距離.
printf("%d\n",dis[n]);
}
}
//對(duì)比也能發(fā)現(xiàn)根本就沒什么兩樣.
附上有臨接鏈表寫的spfa,因位大部分都是用的這種方法寫的,據(jù)說(shuō)是更快,更省內(nèi)存.(如果要寫spfa算法的話,就用這種方法寫,就不要用上面兩種方法了，避免超時(shí)!)
這是水題 poj --- 3013 題目在此的spfa寫法.
(對(duì)于最短路中,dij要T的就一般用spfa了,即對(duì)于點(diǎn)和路比較多的那種用spfa,點(diǎn)比較少的用普通的dij和floyd就行.)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
using namespace std;
const int maxn=1e6+5;
const ll inf=1e15; //這個(gè)inf必須足夠大才行,否則會(huì)一直WA.!!!這是坑點(diǎn),坑了我好久.
int head[maxn];
int weight[maxn];
ll dis[maxn],vis[maxn];
int n,m,ans;
struct node
{
int to;
int v;
int next;
}edge[maxn]; //邊跟點(diǎn)的范圍要分清楚,不要開成一樣的了,否則會(huì)WA!!!
void add(int a,int b,int v)
{
edge[ans].to=b; //a可以到b點(diǎn).
edge[ans].v=v; //v是兩點(diǎn)間的距離.
edge[ans].next=head[a]; //結(jié)束標(biāo)記,表示沒有再于a點(diǎn)相連的點(diǎn)了.
head[a]=ans++;
}
void spfa(int u)
{
queue<int >q;
dis[u]=0;
vis[u]=1;
q.push(u);
while(!q.empty()){
int k=q.front(); //從不斷入隊(duì)中的元素中不斷進(jìn)行循環(huán)的那個(gè)步驟,直到隊(duì)列為空.
//printf("%d\n",k);
q.pop();
vis[k]=0;
for(int i=head[k];i!=-1;i=edge[i].next)//懂不起寫出來(lái)就可以了.
{ //headx表示提取與x直接相連的點(diǎn)的信息.然后直到提取到head為-1時(shí)(初始化值),表示提取完畢,即結(jié)束.(然后進(jìn)行下一個(gè)開頭的提取.)
int m=edge[i].to;
if(dis[m]>dis[k]+edge[i].v){//意思是u點(diǎn)到m點(diǎn)的距離如果大于u點(diǎn)到k點(diǎn)再到m點(diǎn)的距離的話.
dis[m]=dis[k]+edge[i].v;
if(!vis[m]){
vis[m]=1;
q.push(m);
}
}
}
}
}
void solve()
{
CLR(vis);
memset(head,-1,sizeof(head));
ans=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
dis[i]=inf;
scanf("%d",&weight[i]);
}
for(int i=0;i<m;i++){ //因?yàn)檫@個(gè)
int u,v,w;
scanf("%d%d%d",&u,&v,&w);（保證兩個(gè)點(diǎn)之間不會(huì)有多條路）.
add(u,v,w);//因?yàn)槭菬o(wú)向圖,所以要加兩次.
add(v,u,w);
}
spfa(1);
ll ans=0;
int flag=1;
for(int i=2;i<=n;i++){
if(dis[i]==inf){
flag=0;
break;
}
ans+=weight[i]*dis[i];//為什么這樣算也可以得出正確答案,是推出來(lái)的.請(qǐng)看下面
printf("%I64d\n",ans);
}
if(flag)
printf("%I64d\n",ans);
else
printf("No Answer\n");//不能將所有點(diǎn)都連接起來(lái).
}
int main() //用的臨接鏈表做的.速度快,內(nèi)存小.(用的數(shù)組模擬的)
{
int t;
scanf("%d",&t);
while(t--)
solve();
}
/*
第二個(gè)樣例中的計(jì)算方法
4*40+3*50+2*60+3*(20+40+50+60)+2*30+1*(10+20+30+40+50+60)
=10*1+20*(1+3)+30*(2+1)+40*(4+1+3)+50*(3+1+3)+60*(1+2+3)
=10+80+90+320+350+360
=1210
所以得出來(lái)的公式.(ans+=weight[i]*dis[i]).
*/
