有向圖dijkstra演算法
⑴ 用dijkstra演算法計算源點到個結點的最短路徑....謝謝親愛的朋友~ 詳細答案
(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)
1． 置集合S={2,3,...n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊) 2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3
3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2
⑵ 求！最短路徑演算法 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頁
************/
⑶ 狄克斯特拉演算法的path是怎麼算出來的
Dijkstra演算法（狄克斯特拉演算法） Dijkstra演算法是由荷蘭計算機科學家 狄克斯特拉 （ Dijk stra ）於1959 年提出的，因此又叫狄克斯特拉演算法。 是從一個頂點到其餘各頂點的最短路徑演算法， 解決的是有向圖中最短路徑問題。
程序如下，稍加改動即可。
帶權有向圖的最短路徑的求解
//帶權有向圖的最短路徑的求解
#include <stdio.h>
#include <stdlib.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//鄰接矩陣存儲方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉演算法
void Ppath(int path[],int i,int v)
{
⑷ Dijkstra演算法流程圖
定義G=(V,E)，定義集合S存放已經找到最短路徑的頂點，集合T存放當前還未找到最短路徑的頂點，即有T=V-S
Dijkstra演算法描述如下：
(1) 假設用帶權的鄰接矩陣edges來表示帶權有向圖，edges[i][j]表示弧<Vi, Vj>上的權值。若<Vi, Vj>不存在則置edges[i][j]=∞（計算機上用一個允許的最大值代替）。S為已經找到的從Vs出發的最短路徑的終點集合，它初始化為空集。那麼，從Vs出發到圖上其餘各頂點（終點）Vi可能達到的最短路徑長度的初值為：D[i]=deges[s][i] Vi∈V
(2) 選擇Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是當前求得的一條從Vs出發的最短路徑的終點。令S=S∪{Vj}
(3) 修改從Vs出發到集合V-S上任一頂點Vk可達的最短路徑長度。如果D[j]+edges[j][k]<D[k]則修改D[k]為D[k]=D[j]+edges[j][k]
重復操作(2)(3)共n-1次。由此求得從Vs到圖上其餘各頂點的最短路徑。
⑸ 以鄰接表作存儲結構實現求源點到其餘各頂點的最短路徑的Dijkstra演算法
具體演算法為：
//Dijkstra求單源最短路徑
#include<stdio.h>
#define N 20 //圖的頂點最多數
#define MAX 1000
#define MIN -1
typedef int ElemType;//圖的頂點標識，這里為自然數
//圖的結點結構
typedef struct ArcNode{
ElemType adjvex;//圖的頂點 （該弧指向頂點的位置）
struct ArcNode *nextarc;//指向下一條弧的指針
int info//該弧權值
}ArcNode;
//表頭結點表
typedef struct VertexNode{
ElemType data;
ArcNode *firstarc;
}VertexNode;
//圖
typedef struct AdjList{
VertexNode vertex[N];
int vexnum;//圖的頂點數
int arcnum;//弧數;
int kind;//圖的種類（kind=1為有向圖）
int dist[N];//圖的路徑長度
int path[N];//輔助數組
}AdjList;
//邊
typedef struct{
int i;
int j;
int f;
}Side;
//鄰接表法創建圖
int CreateDAG(AdjList *L){
int i,j;
ArcNode *p=NULL;
//測試用例
Side S[N];
S[0].i=1;S[0].j=3;S[0].f=10;
S[1].i=1;S[1].j=5;S[1].f=30;
S[2].i=1;S[2].j=6;S[2].f=100;
S[3].i=2;S[3].j=3;S[3].f=5;
S[4].i=3;S[4].j=4;S[4].f=50;
S[5].i=4;S[5].j=6;S[5].f=10;
S[6].i=5;S[6].j=6;S[6].f=60;
S[7].i=5;S[7].j=4;S[7].f=20;
for(i=1;i<7;i++){
L->vertex[i].data=i;
L->dist[i]=MAX;//設為最大值，表示不可達
L->path[i]=MIN;//設為最小值，表示尚未初始化
//L->vertex[i].indegree=0;
L->vertex[i].firstarc=NULL;
}
L->kind=1;
L->vexnum=6;
L->arcnum=8;
for(i=0;i<8;i++){
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=S[i].j;
p->info=S[i].f;
p->nextarc=L->vertex[(S[i].i)].firstarc;
L->vertex[(S[i].i)].firstarc=p;
if(S[i].i==1){//初始頂點為1
L->dist[(S[i].j)]=S[i].f;
//L->path[(S[i].j)]=S[i].f;
}
// L->vertex[(S[i].j)].indegree++;
}
return 1;
}
//輸出鄰接表存儲
void PrintALGraph(AdjList *L){
ArcNode *p=NULL;
int i,k=0;
for(i=1;i<=L->vexnum;i++){
k=L->vertex[i].data;
printf("V%d",k);
// printf(" 入度為%d 鄰接點有 ",(L->vertex[i].indegree));
p=L->vertex[k].firstarc;
while(p!=NULL){
printf(" ->%d",p->adjvex);
p=p->nextarc;
}
printf(" ");
}
}
//Dijkstra求單源最短路徑
void Dijkstra(AdjList *L){
int i=1,j,k=0;
Side s;
L->path[1]=0;
ArcNode *p=NULL;
while(k<10){
s.f=MAX;
for(i=1;i<=L->vexnum;i++){
if(L->path[i]!=MIN){
p=L->vertex[i].firstarc;
if(p!=NULL){
while(p!=NULL){
if(s.f>p->info&&L->path[(p->adjvex)]==MIN){
s.f=p->info;
s.i=i;
s.j=p->adjvex;
}
p=p->nextarc;
}
}
}
}
if(s.f==MAX){
}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){
L->dist[(s.j)]=L->dist[(s.i)]+s.f;
L->path[(s.j)]=L->dist[(s.j)];
}else{
L->path[(s.j)]=L->dist[(s.j)];
}
k++;
}
//輸出
printf("輸出最短路徑: ");
for(i=1;i<=L->vexnum;i++){
if(L->dist[i]==1000||i==1){
printf("v1到v%d不存在最短路徑 ",i);
}else{
printf("v1到v%d的最短路徑是%d ",i,L->dist[i]);
}
printf("path is %d ",L->path[i]);
}
}
int main(){
AdjList *L=(AdjList *)malloc(sizeof(AdjList));
if(CreateDAG(L)==1){
PrintALGraph(L);
Dijkstra(L);
}else{
printf("創建失敗 ");
}
}
(5)有向圖dijkstra演算法擴展閱讀：
要求帶權有向圖中某一頂點到其他各頂點的最短路徑，常用Dijkstra演算法，該演算法基本思想是，先將圖的頂點分為兩個集合，一個為已求出最短路徑的終點集合（開始為原點v1），另一個為還未求出最短路徑的頂點集合（開始為除v1外的全部結點），然後按最短路徑長度的遞增順序逐個將第二個集合的頂點加到第一組中。
演算法中使用dist數組，dist[i]表示目前已經找到、v1到vi的當前最短路徑，否則為MAX；path數組，作為是否找到該點最短路徑的標志，path[i]==MIN表示為未找到，否則為最短路徑值。
⑹ 用java怎麼用迪傑斯特拉算有向圖有權值的最短路徑
Dijkstra(迪傑斯特拉)演算法是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其採用的是貪心法的演算法策略，大概過程如下：
1.聲明兩個集合，open和close，open用於存儲未遍歷的節點，close用來存儲已遍歷的節點
2.初始階段，將初始節點放入close，其他所有節點放入open
3.以初始節點為中心向外一層層遍歷，獲取離指定節點最近的子節點放入close並從新計算路徑，直至close包含所有子節點
代碼實例如下：
Node對象用於封裝節點信息，包括名字和子節點
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}
MapBuilder用於初始化數據源，返回圖的起始節點
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
圖的結構如下圖所示：
Dijkstra對象用於計算起始節點到所有其他節點的最短路徑
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封裝路徑距離
Map<String,String> pathInfo=new HashMap<String,String>();//封裝路徑信息
public Node init(){
//初始路徑,因沒有A->E這條路徑,所以path(E)設置為Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//將初始節點放入close,其他節點放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距離start節點最近的子節點,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子節點在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前設置的距離大於新計算出來的距離
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重復執行自己,確保所有子節點被遍歷
computePath(nearest);//向外一層層遞歸,直至所有頂點被遍歷
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 獲取與node最近的子節點
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}
Main用於測試Dijkstra對象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}
⑺ dijstra演算法的使用需要哪些條件
Dijstra演算法一般用於權值大於等於零的有向或無向圖，求解單源最短路徑問題
若權值小於零，不能保證得到正確的解
若為無權圖，則應直接使用廣度優先搜索
Dijstra的標准實現是基於有向圖實現的。對於無向圖，可以通過把所有邊都當成雙向連同的有向邊，轉化為有向圖來做
⑻ dijkstra演算法是什麼
Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。
其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。
不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。
Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。
因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。
已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。
⑼ 用Dijkstra演算法求圖中從頂點a到其他各頂點間的最短路徑，並寫出執行演算法過程中各步的狀態。
迪克斯加（Dijkstra）演算法(最短路徑演算法)是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中任意兩個頂點之間的最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
迪科斯徹演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0）， 同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到v的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到u的路徑。這條路徑的長度是d+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d達到它最終的值的時候每條邊(u,v)都只被拓展一次。
演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找權值最小的點為node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各點的權值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.
⑽ 已知帶權有向圖如圖7-29所示,請利用Dijkstra演算法從頂點V4出發到其餘頂點的最短路
初始化d[i]為無窮大，由於從v4開始，所以將d4=0，標記v4已選擇。
下面開始Dijkstra演算法：
和v4相連的且未標記的點有v2和v6，這樣更新d2=20，d6=15，選擇未標記所有點中最小的d6=15，標記v6已選擇，這樣我們算出了v4->v6最短距離d6=15；
從v6開始，和v6相連的且未標記的是v2，此時算d6+6=21>20,所以不更新d2，選擇未標記所有點中最小的d2=20，標記v2已選擇，這樣算出了v4->v2最短距離d2=20；
從v2開始，和v2相連的且未標記的有v1和v5，d1=d2+10=30,d5=d2+30=50，選擇未標記所有點中最小的d1=30，標記v1已選擇，這樣我們算出了v4->v1最短距離d1=30；
從v1開始，和v1相連的且未標記的有v3，d3=d1+15=45，選擇剩下沒被選的所有點的最小的d3=45(d5=50)，標記v3已選擇，這樣我們算出了v4->v3最短距離d3=45
從v3開始，沒有出去的路徑，不更新距離，選擇剩下沒被選的所有點的最小的d5=50，標記v5已選擇，這樣我們算出了v4->v5最短距離d5=50.
此時所有的點都被訪問，結束。
註：上面的標記點已選擇注意下，在演算法的實現中用的是將所有的點放入隊列中，一旦一個點被選擇就是說求出了最短距離，就從此隊列刪除該點，一直到此隊列為空，結束演算法，我寫標記只是為了方便理解。
希望能幫你清晰了解Dijkstra演算法，圖論中很重要的演算法之一。