dijkstra演算法代碼
㈠ 求Dijkstra演算法的源代碼
Dijkstra演算法--c++源代碼--
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
}
/*********
頂點個數用n表示，這里給出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具體例子見 電子工業出版社 《演算法設計技巧與分析》148頁
************/
㈡ 用dijkstra演算法解決最短路徑問題c語言代碼實現時怎樣將每一個路徑的頂點次序依次輸出出來
voidDijkstra(intn,intv,intdist[],intprev[],int**cost)
{
inti;
intj;
intmaxint=65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值
int*s;//定義具有最短路徑的節點子集s
s=(int*)malloc(sizeof(int)*n);
//初始化最小路徑代價和前一跳節點值
for(i=1;i<=n;i++)
{
dist[i]=cost[v][i];
s[i]=0;
if(dist[i]==maxint)
{
prev[i]=0;
}
else
{
prev[i]=v;
}
}
dist[v]=0;
s[v]=1;//源節點作為最初的s子集
for(i=1;i<n;i++)
{
inttemp=maxint;
intu=v;
//加入具有最小代價的鄰居節點到s子集
for(j=1;j<=n;j++)
{
if((!s[j])&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
}
s[u]=1;
//計算加入新的節點後，更新路徑使得其產生代價最短
for(j=1;j<=n;j++)
{
if((!s[j])&&(cost[u][j]<maxint))
{
intnewdist=dist[u]+cost[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
}
}
//展示最佳路徑函數
voidShowPath(intn,intv,intu,int*dist,int*prev)
{
intj=0;
intw=u;
intcount=0;
int*way;
way=(int*)malloc(sizeof(int)*(n+1));
//回溯路徑
while(w!=v)
{
count++;
way[count]=prev[w];
w=prev[w];
}
//輸出路徑
printf("thebestpathis: ");
for(j=count;j>=1;j--)
{
printf("%d->",way[j]);
}
printf("%d ",u);
}
//主函數，主要做輸入輸出工作
voidmain()
{
inti,j,t;
intn,v,u;
int**cost;//代價矩陣
int*dist;//最短路徑代價
int*prev;//前一跳節點空間
printf("pleaseinputthenodenumber:");
scanf("%d",&n);
printf("pleaseinputthecoststatus: ");
cost=(int**)malloc(sizeof(int)*(n+1));
for(i=1;i<=n;i++)
{
cost[i]=(int*)malloc(sizeof(int)*(n+1));
}
//輸入代價矩陣
for(j=1;j<=n;j++)
{
for(t=1;t<=n;t++)
{
scanf("%d",&cost[j][t]);
}
}
dist=(int*)malloc(sizeof(int)*n);
prev=(int*)malloc(sizeof(int)*n);
printf("pleaseinputthesourcenode:");
scanf("%d",&v);
//調用dijkstra演算法
Dijkstra(n,v,dist,prev,cost);
printf("***************************** ");
printf("haveconfirmthebestpath ");
printf("***************************** ");
for(i=1;i<=n;i++)
{
if(i!=v)
{
printf("thedistancecostfromnode%dtonode%dis%d ",v,i,dist[i]);
printf("thepre-nodeofnode%disnode%d ",i,prev[i]);
ShowPath(n,v,i,dist,prev);
}
}
}
㈢ 求！最短路徑演算法 Dijkstra 用C語言編出來
Dijkstra演算法--c++源代碼--by
偉偉豬
[轉貼
2005-12-15
20:21:00
]
發表者:
偉偉豬
/***********************************************
設G=(V,E)是一個每條邊都有非負長度的有向圖，有一個特異的頂點s稱為緣。
單源最短路徑問題，或者稱為最短路徑問題，是要確定從s到V中沒一個其他
頂點的距離，這里從頂點s到x的距離定義為從s到x的最短路徑問題。這個問題
可以用Dijkstra演算法解決。下面我給我了c++下的源代碼！
--by
偉偉豬
************************************************/
#include<iostream.h>
void
main()
{
int
infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input
the
value
of
n:";
cin>>n;
cout<<endl;
d=new
int[n];
s=new
int[n];
p=new
int[n];
w=new
int*[n];
for(i=0;i<n;i++)
{w[i]=new
int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity)
p[i]=0;
else
p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
{t=d[j];k=j;}
s[k]=1;//point
k
join
the
S
for
(j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++)
cout<<d[i]<<"
";
}
/*********
頂點個數用n表示，這里給出的例子n=6
100
1
12
100
100
100
100
100
9
3
100
100
100
100
100
100
5
100
100
100
4
100
13
15
100
100
100
100
100
4
100
100
100
100
100
100
具體例子見
電子工業出版社
《演算法設計技巧與分析》148頁
************/
㈣ C語言實現Dijkstra演算法
#include<stdlib.h> #define INFINITY 1000000000 //最大距離
#define MAX_NODES 1024 //最大節點數
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示從 i 到 j 的距離 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驅節點
int length; //到起始點的距離
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是當前工作節點
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}
㈤ 希望熟悉c++中Dijkstra演算法實現的編程高手們解答！！
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
這個表示的是取到當前最短路是經過哪個點過來的。記錄路徑，如果要輸出路徑的話就一直接prev就可以了。
㈥ 關於最短路的Dijkstra演算法的程序源代碼!
function [l,z]=Dijkstra(W)
n = size (W,1);
for i = 1 :n
l(i)=W(1,i);
z(i)=1;
end
i=1;
while i<=n
for j =1 :n
if l(i)>l(j)+W(j,i)
l(i)=l(j)+W(j,i);
z(i)=j;
if j<i
if j~=1
i=j-1;
else
i=1;
end
end
end
i=i+1;
end
% W =[ 0 2 1 8 Inf Inf Inf Inf
% 2 0 Inf 6 1 Inf Inf Inf
% 1 Inf 0 7 Inf Inf 9 Inf
% 8 6 7 0 5 1 2 Inf
% Inf 1 Inf 5 0 3 Inf 9
% Inf Inf Inf 1 3 0 4 6
% Inf Inf 9 2 Inf 4 0 3
% Inf Inf Inf Inf 9 6 3 0 ];
得到實驗數據結果：
L： 0 2 1 7 3 6 9 12
Z： 1 1 1 6 2 5 4 5
其中L為從1出發的結點到其他各個結點的路徑長度，Z為路徑上的結點，具體路徑可由如下方法獲得：
如查看1號到4號結點的路徑，要經過6號1——》6——》4，而1號到6號要經過5號，即1——》5——》6——》4，進一步1號到5號要經過2號，即1——》2——》5——》6——》4，最後，因為1號可以直接到2號，故最短路徑確定為1——》2——》5——》6——》4。
這裡面加入了if j<i，因為在每次i循環時，i代表的是目的結點，j代表的是通過結點j到達目標結點i，就是說如果當i為5時表示到前幾個目標結點的最短路徑已經確定了，但是如果此時發現經過的結點j《i產生了新的最短路徑，則需要重新確定結點j為目標時的最短路徑。
另附一個對比演算法：
用於求從起始點s到其它各點的最短路
%D為賦權鄰接矩陣，d為s到其它各點最短路徑的長度，DD記載了最短路徑生成樹
function [d,DD]=dijkstra_aiwa(D,s)
[m,n]=size(D);
d=inf.*ones(1,m);
d(1,s)=0;
dd=zeros(1,m);
dd(1,s)=1;
y=s;
DD=zeros(m,m);
DD(y,y)=1;
counter=1;
while length(find(dd==1))<m
for i=1:m
if dd(i)==0
d(i)=min(d(i),d(y)+D(y,i));
end
end
ddd=inf;
for i=1:m
if dd(i)==0&&d(i)<ddd
ddd=d(i);
end
end
yy=find(d==ddd);
counter=counter+1;
DD(y,yy(1,1))=counter;
DD(yy(1,1),y)=counter;
y=yy(1,1);
dd(1,y)=1;
end
㈦ 優先隊列實現dijkstra演算法C++代碼
#include<fstream>
#define MaxNum 765432100
using namespace std;
ifstream fin("Dijkstra.in");
ofstream fout("Dijkstra.out");
int Map[501][501];
bool is_arrived[501];
int Dist[501],From[501],Stack[501];
int p,q,k,Path,Source,Vertex,Temp,SetCard;
int FindMin()
{
int p,Temp=0,Minm=MaxNum;
for(p=1;p<=Vertex;p++)
if ((Dist[p]<Minm)&&(!is_arrived[p]))
{
Minm=Dist[p];
Temp=p;
}
return Temp;
}
int main()
{
memset(is_arrived,0,sizeof(is_arrived));
fin >> Source >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
if (Map[p][q]==0) Map[p][q]=MaxNum;
}
for(p=1;p<=Vertex;p++)
{
Dist[p]=Map[Source][p];
if (Dist[p]!=MaxNum)
From[p]=Source;
else
From[p]=p;
}
is_arrived[Source]=true;
SetCard=1;
do
{
Temp=FindMin();
if (Temp!=0)
{
SetCard=SetCard+1;
is_arrived[Temp]=true;
for(p=1;p<=Vertex;p++)
if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p]))
{
Dist[p]=Dist[Temp]+Map[Temp][p];
From[p]=Temp;
}
}
else
break;
}
while (SetCard!=Vertex);
for(p=1;p<=Vertex;p++)
if(p!=Source)
{
fout << "========================\n";
fout << "Source:" << Source << "\nTarget:" << p << '\n';
if (Dist[p]==MaxNum)
{
fout << "Distance:" << "Infinity\n";
fout << "Path:No Way!";
}
else
{
fout << "Distance:" << Dist[p] << '\n';
k=1;
Path=p;
while (From[Path]!=Path)
{
Stack[k]=Path;
Path=From[Path];
k=k+1;
}
fout << "Path:" << Source;
for(q=k-1;q>=1;q--)
fout << "-->" << Stack[q];
}
fout << "\n========================\n\n";
}
fin.close();
fout.close();
return 0;
}
Sample Input
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
Sample Output
========================
Source:2
Target:1
Distance:20
Path:2-->1
========================
========================
Source:2
Target:3
Distance:25
Path:2-->3
========================
========================
Source:2
Target:4
Distance:50
Path:2-->1-->4
========================
========================
Source:2
Target:5
Distance:50
Path:2-->3-->5
========================
========================
Source:2
Target:6
Distance:60
Path:2-->3-->5-->6
========================
========================
Source:2
Target:7
Distance:Infinity
Path:No Way!
========================
示常式序及相關子程序：
void Dijkstra(int n,int[] Distance,int[] iPath)
{
int MinDis,u;
int i,j;
//從鄰接矩陣復制第n個頂點可以走出的路線，就是復制第n行到Distance[]
for(i=0;i<VerNum;i++)
{
Distance=Arc[n,i];
Visited=0;
}//第n個頂點被訪問，因為第n個頂點是開始點
Visited[n]=1;
//找到該頂點能到其他頂點的路線、並且不是開始的頂點n、以前也沒走過。
//相當於尋找u點，這個點不是開始點n
for(i=0;i<VerNum;i++)
{
u=0;
MinDis=No;
for(j=0;j<VerNum;j++)
if(Visited[j] == 0&&(Distance[j]<MinDis))
{
MinDis=Distance[j];
u=j;
}
//如範例P1871圖G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2
//找完了，MinDis等於不連接，則返回。這種情況類似V5。
if(MinDis==No) return ;
//確立第u個頂點將被使用，相當於Arc[v,u]+Arc[u,w]中的第u頂點。
Visited[u]=1;
//尋找第u個頂點到其他所有頂點的最小路，實際就是找Arc[u,j]、j取值在[0，VerNum]。
//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，則Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
//實際中，因為Distance[]是要的結果，對於起始點確定的情況下，就是：
//如果(Distance[u] + Arc[u,j]) <= Distance[j] 則：
//Distance[j] = Distance[u] + Arc[u, j]；
//而iPath[]保存了u點的編號；
//同理：對新找出的路線，要設置Visited[j]=0，以後再找其他路，這個路可能別利用到。例如V3
for(j=0;j<VerNum;j++)
if(Visited[j]==0&&Arc[u,j]<No&&u!= j)
{
if ((Distance[u] + Arc[u,j]) <= Distance[j])
{
Distance[j] = Distance[u] + Arc[u, j];
Visited[j]=0;
iPath[j] = u;
}
}
}
}
//輔助函數
void Prim()
{
int i,m,n=0;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
}
Visited[n]++;
listBox1.Items.Add (V[n]);
while(Visit()>0)
{
if((m=MinAdjNode(n))!=-1)
{
T[n].Nodes.Add(T[m]);
n=m;
Visited[n]++;
}
else
{
n=MinNode(0);
if(n>0) T[Min2].Nodes.Add(T[Min1]);
Visited[n]++;
}
listBox1.Items.Add (V[n]);
}
treeView1.Nodes.Add(T[0]);
}
void TopoSort()
{
int i,n;
listBox1.Items.Clear();
Stack S=new Stack();
for(i=0;i<VerNum;i++)
Visited=0;
for(i=VerNum-1;i>=0;i--)
if(InDegree(i)==0)
{
S.Push(i);
Visited++;
}
while(S.Count!=0)
{
n=(int )S.Pop();
listBox1.Items.Add (V[n]);
ClearLink(n);
for(i=VerNum-1;i>=0;i--)
if(Visited==0&&InDegree(i)==0)
{
S.Push(i);
Visited++;
}
}
}
void AOETrave(int n,TreeNode TR,int w)
{
int i,w0;
if(OutDegree(n)==0) return;
for(i=0;i<VerNum;i++)
if((w0=Arc[n,i])!=0)
{
listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());
TreeNode T1=new TreeNode();
T1.Text =V+" [W="+(w+w0).ToString()+"]";
TR.Nodes.Add(T1);
AOETrave(i,T1,w+w0);
}
}
void AOE()
{
int i,w=0,m=1;
TreeNode T1=new TreeNode();
for(i=0;i<VerNum;i++)
{
Visited=0;
}
T1.Text =V[0];
listBox1.Items.Add ("雙親表示法顯示這個生成樹：");
listBox1.Items.Add ("V\tW\tID\tPID");
for(i=0;i<VerNum;i++)
{
if((w=Arc[0,i])!=0)
{
listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");
TreeNode T2=new TreeNode();
T2.Text=V+" [W="+w.ToString()+"]";
AOETrave(i,T2,w);
T1.Nodes.Add (T2);
listBox1.Items.Add("\t\t樹"+m.ToString());
m++;
}
}
treeView1.Nodes.Clear();
treeView1.Nodes.Add (T1);
}
int IsZero()
{
int i;
for(i=0;i<VerNum;i++)
if(LineIsZero(i)>=0) return i;
return -1;
}
int LineIsZero(int n)
{
int i;
for(i=0;i<VerNum;i++)
if (Arc[n,i]!=0) return i;
return -1;
}
void DepthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
R=0;
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m]);
R[m]=1;
}
Visited[m]++;
DTrave(m);
}
for(i=0;i<VerNum;i++)
{
if(R==1)
treeView1.Nodes.Add (T);
}
}
void DTrave(int n)
{
int i;
if (LineIsZero(n)<0) return;
for(i=VerNum-1;i>=0;i--)
if(Arc[n,i]!=0)
{
Arc[n,i]=0;
Arc[i,n]=0;
if(Visited==0)
{
listBox1.Items.Add (V);
T[n].Nodes.Add (T);
R=0;
}
Visited++;
DTrave(i);
}
}
void BreadthTraverse()
{
int i,m;
for(i=0;i<VerNum;i++)
{
Visited=0;
T=new TreeNode();
T.Text =V;
R=0;
}
while((m=IsZero())>=0)
{
if(Visited[m]==0)
{
listBox1.Items.Add (V[m]);
R[m]=1;
}
Visited[m]++;
BTrave(m);
}
for(i=0;i<VerNum;i++)
{
if(R==1)
treeView1.Nodes.Add (T);
}
}
void BTrave(int n)
{
int i;
Queue Q=new Queue();
Q.Enqueue(n);
while(Q.Count!=0)
{
for(i=0;i<VerNum;i++)
{
if(Arc[n,i]!=0)
{
Arc[n,i]=0;
Arc[i,n]=0;
if(Visited==0)
{
listBox1.Items.Add(V);
T[n].Nodes.Add (T);
R=0;
}
Visited++;
Q.Enqueue(i);
}
}
n=(int )Q.Dequeue();
}
}
int MinNode(int vn)
{
int i,j,n,m,Min=No;
n=-1;m=-1;
for (i=vn;i<VerNum;i++)
for(j=0;j<VerNum;j++)
if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited==0&&Visited[j]==1)
{
Min=Arc[i,j];n=i;m=j;
}
Min1=n;Min2=m;
return n;
}
int MinAdjNode(int n)
{
int i,Min,m;
Min=No;m=-1;
for(i=0;i<VerNum;i++)
if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1)
{
Min=Arc[n,i];m=i;
}
return m;
}
int Visit()
{
int i,s=0;
for(i=0;i<VerNum;i++)
if(Visited==0) s++;
return s;
}
[編輯本段]dijkstra演算法的Pascal實現：
program dijkstra;
var
a:array[1..100,1..100]of integer;
flag:array[1..100]of boolean;
w,x,n,i,j,min,minn:integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
fillchar(flag,sizeof(flag),false);
flag[1]:=true;
minn:=1;
for x:=2 to n do
begin
min:=32767;
for i:=2 to n do
if (a[1,i]<min)and(flag=false) then
begin
min:=a[1,i];
minn:=i;
end;
flag[minn]:=true;
for j:=1 to n do
if (j<>minn) and (a[1,minn]+a[minn,j]<a[1,j]) and(flag[j]=false) then
a[1,j]:=a[1,minn]+a[minn,j];
end;
for i:=1 to n do
write(a[1,i],' ');
end.
4
0 100 30 999
100 0 99 10
30 99 0 99
999 10 99 0
程序輸出：0 100 30 110
dijkstra演算法的MATLAB實現：
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';
pb(1:length(a))=0;pb(i)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=M;d(i)=0;temp=1;
while sum(pb)<length(a)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(i));
pb(temp)=1;
index1=[index1,temp];
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2
matlab編程
function [s,d]=minroute(i,m,w,opt)
% 圖與網路論中求最短路徑的dijkstra演算法M函數
% 格式[s,d]=minroute(i,m,w,opt)
if nargin<4,opt=0;end
dd=[];tt=[];ss=[];ss(1,1)=i;v=1:m;v(i)=[];
dd=[0;i];kk=2;[mdd,ndd]=size(dd);
while~isempty(v)
[tmpd,j]=min(w(i,v));tmpj=v(j);
for k=2:ndd
[tmp2,jj]=min(dd(1,k)+w(dd(2,k),v));
tmp2=v(jj);tt(k-1,:)=[tmp1,tmp2,jj];
end;
tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(;,1));
if tmp3==tmpd
ss(1:2,kk)=[i;tmp(tmp4,2)];
else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);
if dd(2,tmp4)=ss(tmp6,tmp4)
ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];
else,ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];
end;end
dd=[dd,[tmp3,tmp(tmp4,2)]];v(tmp(tmp4,3))=[];
[mdd,ndd]=size(dd);kk=kk+1;
end;
if opt==1
[tmp,t]=sort(dd(2,:));s=ss(:t);d=dd(1,t);
else,s=ss;d=dd(1,:);
end
㈧ 急求dijkstra演算法的程序
演算法基本思想
設S為最短距離已確定的頂點集（看作紅點集），V-S是最短距離尚未確定的頂點集（看作藍點集）。
①初始化
初始化時，只有源點s的最短距離是已知的(SD(s)=0)，故紅點集S={s}，藍點集為空。
②重復以下工作，按路徑長度遞增次序產生各頂點最短路徑
在當前藍點集中選擇一個最短距離最小的藍點來擴充紅點集，以保證演算法按路徑長度遞增的次序產生各頂點的最短路徑。
當藍點集中僅剩下最短距離為∞的藍點，或者所有藍點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。
注意：
①若從源點到藍點的路徑不存在，則可假設該藍點的最短路徑是一條長度為無窮大的虛擬路徑。
②從源點s到終點v的最短路徑簡稱為v的最短路徑；s到v的最短路徑長度簡稱為v的最短距離，並記為SD(v)。
（3）在藍點集中選擇一個最短距離最小的藍點k來擴充紅點集
根據按長度遞增序產生最短路徑的思想，當前最短距離最小的藍點k的最短路徑是：
源點，紅點1，紅點2，…，紅點n，藍點k
距離為：源點到紅點n最短距離+<紅點n,藍點k>邊長
為求解方便，設置一個向量D[0．．n-1]，對於每個藍點v∈
V-S，用D[v]記錄從源點s到達v且除v外中間不經過任何藍點(若有中間點，則必為紅點)的"最短"路徑長度（簡稱估計距離）。
若k是藍點集中估計距離最小的頂點，則k的估計距離就是最短距離，即若D[k]=min{D[i]
i∈V-S}，則D[k]=SD(k)。
初始時，每個藍點v的D[c]值應為權w<s，v>，且從s到v的路徑上沒有中間點，因為該路徑僅含一條邊<s，v>。
注意：
在藍點集中選擇一個最短距離最小的藍點k來擴充紅點集是Dijkstra演算法的關鍵
（4）k擴充紅點集s後，藍點集估計距離的修改
將k擴充到紅點後，剩餘藍點集的估計距離可能由於增加了新紅點k而減小，此時必須調整相應藍點的估計距離。
對於任意的藍點j，若k由藍變紅後使D[j]變小，則必定是由於存在一條從s到j且包含新紅點k的更短路徑：P=<s，…，k，j>。且D[j]減小的新路徑P只可能是由於路徑<s，…，k>和邊<k，j>組成。
所以，當length(P)=D[k]+w<k，j>小於D[j]時，應該用P的長度來修改D[j]的值。
（5）Dijkstra演算法
Dijkstra(G，D，s){
//用Dijkstra演算法求有向網G的源點s到各頂點的最短路徑長度
//以下是初始化操作
S={s}；D[s]=0；
//設置初始的紅點集及最短距離
for(
all
i∈
V-S
)do
//對藍點集中每個頂點i
D[i]=G[s][i]；
//設置i初始的估計距離為w<s，i>
//以下是擴充紅點集
for(i=0;i<n-1;i++)do{//最多擴充n-1個藍點到紅點集
D[k]=min{D[i]：all
i
V-S}；
//在當前藍點集中選估計距離最小的頂點k
if(D[k]等於∞)
return；
//藍點集中所有藍點的估計距離均為∞時，
//表示這些頂點的最短路徑不存在。
S=S∪{k}；
//將藍點k塗紅後擴充到紅點集
for(
all
j∈V-S
)do
//調整剩餘藍點的估計距離
if(D[j]>D[k]+G[k][j])
//新紅點k使原D[j]值變小時，用新路徑的長度修改D[j]，
//使j離s更近。
D[j]=D[k]+G[k][j]；
}
}
㈨ 求Dijkstra演算法的C語言實現
//Dijkstra演算法 C語言實現 2008-08-26 12:07 #include<stdio.h>
#include<stdlib.h> #define INFINITY 1000000000 //最大距離
#define MAX_NODES 1024 //最大節點數
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示從 i 到 j 的距離 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驅節點
int length; //到起始點的距離
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是當前工作節點
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}