dijkstra最短路徑演算法
Ⅰ 用迪傑斯特拉演算法計算最短路徑
給定一個有向圖，求v1到其他各節點的最短路徑長度，以及最短路徑。
要求：對dijkstra演算法進行補充，使新演算法在找出這些最短路徑長度的同時，也能求出路徑上的節點序列。
輸入：一個有向帶權圖
這里寫圖片描述
輸出的基本形式如下：
這里寫圖片描述
Ⅱ 運籌學用dijkstra演算法求最短路徑
就是通過廣度搜索遍歷當前節點和子節點的關系，然後再依次遞歸。
我給你開個頭啊:
首先設首節點為1,那麼子節點是2,3,4,那麼我分別遍歷
1-2 = 4
1-3 = 5
1-4 = 2
全部遍歷完後我在從下面的第一個子節點開始遍歷,
1(-2)-5 = 11
1(-2)-3 = 10 和1-3 = 5 對比 5<10 那麼 1-3 = 5
1(-3)-2 = 11 和1-2 = 4進行對比 4<11 那麼1-2 = 4
1(-3)-6 = 14
1(-3)-4 = 6 和 1-4 = 2進行對比 2< 6 那麼 1-4 =2
1(-4)-3 = 3 和 1-3=5 進行對比 5 > 3 那麼 1-3 = 3
.......................
依次遍歷完整個圖
最開始設1 到其他點的路徑為無限大，
然後依次遍歷，if( ( 1到當前點的路徑 + 當前點到某子節點的路徑) < (1 到該子節點的路徑) )
1到該子節點的路徑 = 1到當前點的路徑 + 當前點到該子節點的路徑)
Ⅲ Dijkstra最短路徑演算法 求助
1. 可以取第一個最小的或者取最後一個最小的
2. 這個取的先後對最終的結果沒有影響
Ⅳ 求！Dijkstra演算法計算兩點之間最短路徑的過程， 萬分感謝啊。
假設Mdis[v]表示從原點到節點V的最短路徑長度，通過以下演算法確定從原點出發的單源最短路徑。
1、選擇一個還未擴展過的Mdis值最小的節點V*
2、通過節點V*所連接的每一條邊執行鬆弛操作，i.e. mdis[k] = min{mdis[k], mdis[v] + cost<v, k>}
3、標記節點V為已擴展過，重復第一步直到所有節點都擴展過。
以上演算法的時間復雜度為O(n^2)，可以通過二叉堆優化到O(mlogn)
Ⅳ 求出最短路徑，要過程，用Dijkstra演算法。。。
從v1開始遍歷
v2 = 2;
v3 = 5;
v2較小所以跳到v2
v3 = 4;
v4 = 6;
v5 = 8;
v3較小所以跳到v3
v4 = 5;
v6 = 7;
v4較小所以跳到v4
v6 = 6;
v7 = 9;
v6較小所以跳到v6
v7 = 8;
所以最後結果v1 -> v7最短路徑為v1->v2->v3->v4->v6->v7,最短路徑長度為8
Ⅵ Dijkstra演算法算最短路徑
////////////////////////////////////////////////////////////
// Graph.h
#pragma once
#define maxPoint 100
class CGraph
{
public:
CGraph(void);
~CGraph(void);
bool SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size );
bool Dijkstra();
void Display();
int GetStartPoint();
double GetBestWay( int dest , int path[] , int &pathLen );
private:
//標志當前圖是否已經求解
bool solved;
//當前圖布局
double graph[maxPoint][maxPoint];
//地圖大小
int size;
//起點
int startPoint;
//當前圖的解
double dist[maxPoint];
int prev[maxPoint];
};
////////////////////////////////////////////////////////////
// Graph.cpp
#include 'StdAfx.h'
#include '.\graph.h'
CGraph::CGraph(void)
{
for( int i = 0 ; i < maxPoint ; i++ )
{
for( int j = 0 ; j < maxPoint ; j++ )
graph[i][j] = -1;
}
startPoint = -1;
size = -1;
//當前圖還沒有求解
solved = false;
}
CGraph::~CGraph(void)
{
}
//
//
bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )
{
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
graph[i][j] = g[i][j];
}
this->startPoint = startPoint;
this->size = size;
solved = false;
Dijkstra();
return true;
}
//
//
bool CGraph::Dijkstra()
{
bool s[maxPoint];
for( int j = 0 ; j < size ; j++ )
{
dist[j] = graph[startPoint][j];
s[j] = false;
//dist[i]<0，表示沒有路徑連接 結點startPoint 與 結點j
if( dist[j] < 0 )
prev[j] = 0;
else
prev[j] = startPoint;
}
//從起點出發
dist[startPoint] = 0;
s[startPoint] = true;
for( int i = 0 ; i < size ; i++ )
{
double temp;
int u = startPoint;
bool flag = false;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] )
{
//如果不是第一次比較，temp u，都已經賦值，則
if( flag )
{
if( dist[j] > 0 && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
else
{
u = j;
temp = dist[j];
flag = true;
}
}
}
s[u] = true;
for( int j = 0 ; j < size ; j++ )
{
if( !s[j] && graph[u][j] > 0 )
{
double newDist = dist[u] + graph[u][j];
if( dist[j] < 0 || newDist < dist[j] )
{
dist[j] = newDist;
prev[j] = u;
}
}
}
}
//標記當前問題已經解決
solved = true;
return true;
}
//
//
void CGraph::Display()
{
printf( '當前地圖的鄰接矩陣\n' );
for( int i = 0 ; i < size ; i++ )
{
for( int j = 0 ; j < size ; j++ )
{
printf( '%5.f' , graph[i][j] );
}
printf( '\n' );
}
}
//
//
double CGraph::GetBestWay( int dest , int path[] , int &pathLen )
{
int p = dest;
int theway[maxPoint];
int len = 0;
while( p != startPoint )
{
theway[len] = p;
p = prev[p];
len++;
}
theway[len] = startPoint;
len++;
for( int i = 0 , j = len - 1 ; i < len ; i++ , j-- )
path[i] = theway[j];
pathLen = len;
return dist[dest];
}
//
//
int CGraph::GetStartPoint()
{
return startPoint;
}
//
////////////////////////////////////////////////////////////
// Dijkstra.cpp : 定義控制台應用程序的入口點。
//
#include 'stdafx.h'
#include 'conio.h'
#include 'Graph.h'
int _tmain(int argc, _TCHAR* argv[])
{
double graph[][maxPoint] =
{
{ 1 , 10 , -1 , 30 , 100 } ,
{ -1 , 0 , 50 , -1 , -1 } ,
{ -1 , -1 , 0 , -1 , 10 } ,
{ -1 , -1 , 20 , 0 , 60 } ,
{ -1 , -1 , -1 , -1 , -1 }
};
int size = 5;
int start = 0;
int dest = 1;
int pathlen;
int path[maxPoint];
double dist;
CGraph g;
g.SetGraph( graph , start , size );
g.Display();
printf( '----------------------------------------\n' );
for( dest = 0 ; dest < size ; dest++ )
{
dist = g.GetBestWay( dest , path , pathlen );
printf( '從 %d 到 %d 的最短路徑長 %.f\n' , g.GetStartPoint() , dest , dist );
printf( '所經結點為:\n' );
for( int i = 0 ; i < pathlen ; i++ )
printf( '%3d' , path[i] );
printf( '\n----------------------------------------\n' );
}
getch();
return 0;
}
////////////////////////////////////////////////////////////
// 程序說明：
// 本程序在 VC++.NET 2003 上調試通過
// 首先建立 Win32控制台應用程序，工程名為 Dijkstra
// 工程設置默認
// 添加 一般C++類 CGraph
// 填寫以上內容
Ⅶ 最短路徑（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;
不是已經有答案了嗎?還問什麼呢
Ⅷ 數據結構 dijkstra演算法 最短路徑
你這個演算法到這步，還沒結束。
因為S=【1,2,4】，U=【3】。下面應該把【3】，加入到S中。進行路徑的判斷。
3加入進來，發現1-》2-》4大於1-》3-》4。所以1-》4的距離會重新算。
Ⅸ 迪傑斯特拉演算法求最短路徑題怎麼做
最早的路徑題，這個在做的時候，你可以通過練習一個函數關系式就能夠進行，把它簡單的測量出來的還是比較簡單的。