最短路徑dijkstra演算法課程設計

『壹』 最短路徑（Dijkstra演算法）

0<-->2 = 667;
0<-->5 = 689;
0<-->9 = 1160;
0<-->13 = 1046;
1<-->13 = 242;
2<-->3 = 3036;
3<-->11 = 1892;
4<-->8 = 1180;
4<-->9 = 303;
4<-->14 = 825;
5<-->6 = 898;
5<-->9 = 695;
5<-->10 = 511;
6<-->7 = 707;
6<-->12 = 1419;
6<-->14 = 482;
7<-->8 = 1588;
10<-->11 = 676;
10<-->12 = 1346;
不是已經有答案了嗎?還問什專么呢屬

『貳』 C++課程設計 dijkstra演算法 並行最短路徑

Dijkstra演算法的思想是DP +貪婪。
每次尋找最近的點，擴大和更新的狀態

為（i = 1; <N; + +）/ /擴展N-1
{
T =無窮內大;
K = 1;
為（J = 1，J <N，J + +）/ /這里容是為了找到最近的點，D最小< （/（[J]）&&（D [J] T [K]））

{
噸= D [J];
K =?
}
[K] = 1 ;/ / k點加入的S
（J = 1，J <N，J + +）
（（！ [J]）&&（D [J]>的D [k] + W [K] [J]））/ /更新狀態......基於動態規劃
{
D [J] =的D [k] + W [K] [J];
P [J] = K;
}
>}

不知道LZ在哪裡目前還不清楚

『叄』 關於求最短路徑的Dijkstra演算法的程序源代碼

下面是在網路上找到的一篇，已經發到你的郵箱裡面了：）
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頁
************/

『肆』 dijkstra演算法 最短路徑

沒有影響啊。。。只要是最小的就行了，反正選擇的總是最小的路徑

『伍』 哪位高手可以幫我寫一個dijkstra最短路徑的演算法。最好是簡單且能運行。主要是想學習這個演算法的主要思想。

#include "stdio.h"
#define M 150
#define X 1000

int main()
{
int i,s,n,j,y,w;
int a[M][M],l[M],d[M],final[M];
while(scanf("%d",&s)>0)
{
if(s==0)
break;
for(i=0;i<s;i++)
for(j=0;j<s;j++)
a[i][j]=X;
for(i=0;i<s;i++)
{
a[i][i]=0;
scanf("%d",&n);
for(j=0;j<n;j++)
{
scanf("%d%d",&y,&w);
a[i][y-1]=w;
}
}
for(i=0;i<s;i++)//以每個點為起點求一次最短路
{
for(j=0;j<s;j++)
final[j]=0;
for(j=0;j<s;j++)
d[j]=a[i][j];
for(j=0;j<s-1;j++)//這里開始是最短路
{
n=X;w=j;
final[i]=1;
for(y=0;y<s;y++)
{
if(d[y]<n&&(!final[y]))
{
n=d[y];
w=y;
}
}
final[w]=1;
for(y=0;y<s;y++)
{
if(d[y]>d[w]+a[w][y]&&(!final[y]))
d[y]=d[w]+a[w][y];
}
}
n=0;
for(j=0;j<s;j++)
{
if(d[j]>n)
n=d[j];
}
l[i]=n;
}
n=M+1;
for(i=0;i<s;i++)
{
if(l[i]<n)
{
y=i;n=l[i];
}
}
if(n<M)
printf("%d %d\n",y+1,n);
else
printf("disjoint\n");
}
return 0;
}
題目是poj1125
該代碼來自博客http://martinblack954.blog.163.com/blog/static/18610521020114288387821/

『陸』 數據結構課程設計—最短路徑

#include <stdio.h>

#define INFINITY 10000
#define TRUE 1
#define FALSE 0
#define VERTEX_NUM 6

typedef struct Graph
{
char vexs[VERTEX_NUM]; /*頂點*/
int arcs[VERTEX_NUM][VERTEX_NUM]; /*鄰接矩陣*/
int vexnum; /*頂點數專*/
int arcnum; /*弧數屬*/
}Graph;

『柒』 用Dijkstra演算法求最短路徑

#include <stdio.h>
#include <string.h>
#define MAX 20
int mincost(int V[], int D[], int n);
int main()
{
int C[MAX][MAX];
int D[MAX], V[MAX] = { 0 }; /*數組V用來表示每次計算加入集合V的點，1為加入了，0為還沒有加入*/
int n, i, j, k, w, sum;
printf("請輸入頂點個數:");
scanf("%d", &n);
printf("\n請輸入建立後的臨接矩陣(用n*n矩陣表示), 輸入100000表示無窮大:\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &C[i][j]);
}
}
V[1] = 1; /*1為源點*/
for(i = 1; i <= n; i++)
{
D[i] = C[1][i]; /*D置初值*/
}
for(i = 1; i <= n; i++)
{
/*從集合S(即沒有經過計算的點）中選出一個點w（即V中值為0），使D[w]值最小*/
w = mincost(V, D, n);
V[w] = 1;
/*由於w的選定，S中的每個點(即V中值為0的點都要重新計算其到源點的最小值*/
for(k = 2; k <= n; k++)
{
if(V[k] == 0)
{
sum = D[w] + C[w][k];
if(sum < D[k])
{
D[k] = sum;
}
}
}
}
for(i = 2; i <= n; i++)
{
printf("D[%d] = %d\n", i, D[i]);
}
memset(V, 0, MAX * sizeof(int)); /*初始化*/
return 0;
}

int mincost(int V[], int D[], int n)
{
int temp = 10000000, i, w = 2;
for(i = 2;i <= n; i++)
{
if(V[i] == 0 && D[i] < temp)
{
temp = D[i];
w = i;
}
}
return w;
}

改成文件的就行了

『捌』 Dijkstra演算法程序怎樣輸出最短路徑

可以去下面這看內看容
http://zengwu3915.blog.163.com/blog/static/278348972009109101834282

『玖』 怎樣用DIJKSTRA演算法設計最短路徑

以下................

輸入時，將s,t,x,y,z五個點按照1,2,3,4,5起別名，輸入格式按照下圖例所示
當提示Please enter the vertex where Dijkstra algorithm starts:時輸入演算法的起始點
比如計算結果v1v4v2表示從點1到點2經過1，4，2為最短路徑
Dijkstra演算法的完整實現版本，演算法的源代碼
/* Dijkstra.c

Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex[0]='v';
lin->vertex[1]='0'+temp;
lin->vertex[2]='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:\n");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i<total;i++)
{
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex[1]==now->vertex[1])
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex[1];
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)<searc->cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path[0]='v';
searc->path[1]=now->vertex[1];
searc->path[2]='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost<min)
{
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex[1]-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex[1]-'0')!=start&&p!=NULL)
{
while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("\n%s",p->vertex);
return OK;
}