迪克斯特拉演算法python實現的簡單介紹

本文目錄一覽：

• 1、python networkx模塊裡面計算最短路徑時，如何處理等價路徑？我怎麼測試只能顯示1條路徑，請大神賜教。
• 2、編程語言的問題
• 3、C語言迪克斯特拉演算法，誰能給點思路
• 4、離散數學中用迪克斯特拉演算法求出a到z的最短路徑，詳細的解答過程
• 5、結構化程序實現的基本原理
• 6、普里姆演算法是什麼?

python networkx模塊裡面計算最短路徑時，如何處理等價路徑？我怎麼測試只能顯示1條路徑，請大神賜教。

if source is None: if target is None: ## Find paths between all pairs. if weight is None: paths=nx.all_pairs_shortest_path(G) else: paths=nx.all_pairs_dijkstra_path(G,weight=weight) else: ## Find paths from all nodes co-accessible to the target. directed = G.is_directed() if directed: G.reverse(copy=False) if weight is None: paths=nx.single_source_shortest_path(G,target) else: paths=nx.single_source_dijkstra_path(G,target,weight=weight) # Now flip the paths so they go from a source to the target. for target in paths: paths[target] = list(reversed(paths[target])) if directed: G.reverse(copy=False) else: if target is None: ## Find paths to all nodes accessible from the source. if weight is None: paths=nx.single_source_shortest_path(G,source) else: paths=nx.single_source_dijkstra_path(G,source,weight=weight) else: ## Find shortest source-target path. if weight is None: paths=nx.bidirectional_shortest_path(G,source,target) else: paths=nx.dijkstra_path(G,source,target,weight)

編程語言的問題

結構化程序設計由迪克斯特拉(E.W.dijkstra)在1969年提出，是以模塊化設計為中心，將待開發的軟體系統劃分為若干個相互獨立的模塊，這樣使完成每一個模塊的工作變單純而明確，為設計一些較大的軟體打下了良好的基礎。

由於模塊相互獨立，因此在設計其中一個模塊時，不會受到其它模塊的牽連，因而可將原來較為複雜的問題化簡為一系列簡單模塊的設計。模塊的獨立性還為擴充已有的系統、建立新系統帶來了不少的方便，因為我們可以充分利用現有的模塊作積木式的擴展。

按照結構化程序設計的觀點，任何演算法功能都可以通過由程序模塊組成的三種基本程序結構的組合: 順序結構、選擇結構和循環結構來實現。

結構化程序設計的基本思想是採用”自頂向下，逐步求精”的程序設計方法和”單入口單出口”的控制結構。自頂向下、逐步求精的程序設計方法從問題本身開始，經過逐步細化，將解決問題的步驟分解為由基本程序結構模塊組成的結構化程序框圖；”單入口單出口”的思想認為一個複雜的程序，如果它僅是由順序、選擇和循環三種基本程序結構通過組合、嵌套構成，那麼這個新構造的程序一定是一個單入口單出口的程序。據此就很容易編寫出結構良好、易於調試的程序來。

面向對象編程（Object Oriented Programming，OOP，面向對象程序設計）是一種計算機編程架構。OOP 的一條基本原則是計算機程序是由單個能夠起到子程序作用的單元或對象組合而成。OOP 達到了軟體工程的三個主要目標：重用性、靈活性和擴展性。為了實現整體運算，每個對象都能夠接收信息、處理數據和向其它對象發送信息。OOP 主要有以下的概念和組件：

組件 － 數據和功能一起在運行著的計算機程序中形成的單元，組件在 OOP 計算機程序中是模塊和結構化的基礎。

抽象性 － 程序有能力忽略正在處理中信息的某些方面，即對信息主要方面關注的能力。

封裝 － 也叫做信息封裝：確保組件不會以不可預期的方式改變其它組件的內部狀態；只有在那些提供了內部狀態改變方法的組件中，才可以訪問其內部狀態。每類組件都提供了一個與其它組件聯繫的介面，並規定了其它組件進行調用的方法。

多態性 － 組件的引用和類集會涉及到其它許多不同類型的組件，而且引用組件所產生的結果得依據實際調用的類型。

繼承性 － 允許在現存的組件基礎上創建子類組件，這統一併增強了多態性和封裝性。典型地來說就是用類來對組件進行分組，而且還可以定義新類為現存的類的擴展，這樣就可以將類組織成樹形或網狀結構，這體現了動作的通用性。

由於抽象性、封裝性、重用性以及便於使用等方面的原因，以組件為基礎的編程在腳本語言中已經變得特別流行。Python 和 Ruby 是最近才出現的語言，在開發時完全採用了 OOP 的思想，而流行的 Perl 腳本語言從版本5開始也慢慢地加入了新的面向對象的功能組件。用組件代替「現實」上的實體成為 JavaScript（ECMAScript） 得以流行的原因，有論證表明對組件進行適當的組合就可以在英特網上代替 HTML 和 XML 的文檔對象模型（DOM）。

C語言迪克斯特拉演算法，誰能給點思路

///求單源最短路徑

#include stdio.h

#include string.h

#define maxint 1000

int dist[maxint] ;

int prev[maxint] ;

int inta[maxint][maxint] ; //原始數據

// prev[] 保存某個點的前驅點的下標

// dist[] 保存源點到其餘點的距離

void Dijkstra(int n , int v , int s[][maxint] )

{

bool check[maxint] ;

int i , j ;

for( i = 1 ; i = n ; i ++ )

{

dist[i] = s[v][i] ;

check[i] = false ;

if( dist[i] == maxint )

prev[i] = 0 ;

else

prev[i] = v ;

}

dist[v] = 0 ;

prev[v] = 0 ;

check[v] = true ;

for ( i = 1 ; i n ; i++ )

{

int temp = maxint ;

int u = v ;

for ( j =1 ; j = n ; j++ )

if( !check[j] dist[j] temp )

{

u = j ;

temp = dist[j] ;

}

check[u] = true ;

for( j = 1 ; j = n ; j++ )

if( !check[j] s[u][j] maxint )

{

int newdist = dist[u] + s[u][j] ;

if( newdist dist[j] )

{

dist[j] = newdist ;

prev[j] = u ;

}

}

}

}

int main()

{

int i , j ;

int n ;

while (scanf(“%d”,n) )

{

memset(prev , 0 ,sizeof(prev) ) ;

memset(dist , 0 ,sizeof(dist) ) ;

for( i = 1 ; i = n ; i ++ )

for( j =1 ; j = n ; j++ )

{

if ( i == j )

inta[i][j] = 0 ;

else

inta[i][j] = maxint ;

}

int a , b , c ;

while(scanf(“%d %d %d”,a, b ,c ) )

{

if( a == 0 b == 0 c == 0 )

break ;

inta[a][b] = c ;

}

int v ;

scanf(“%d”,v) ;

Dijkstra(n, v ,inta ) ;

printf(“Index aid prev\n”) ;

for( i =1 ; i = n ; i++ )

printf(“%-10d %-10d %-10d\n”,i ,dist[i] , prev[i] ) ;

/* for( i =1 ; i = n; i ++ )

printf(“%d “,dist[i] );

printf(“\n”);

for( i = 1 ; i = n ; i++ )

printf(“%d “,prev[i] ) ;

*/

printf(“\n\n”) ;

}

return 0 ;

}

/* 運行結果 ：

5

1 2 10

1 4 30

1 5 100

2 3 50

3 5 10

4 3 20

4 5 60

0 0 0

1

Index aid prev

1 0 0

2 10 1

3 50 4

4 30 1

5 60 3

*/

離散數學中用迪克斯特拉演算法求出a到z的最短路徑，詳細的解答過程

離散數學中用迪克斯特拉演算法求出a到z的最短路徑，詳細的解答過程

最短距離是8，不過你圖中沒有中間結點的標號，不好說明哦

離散數學中用迪克斯特拉演算法求出a到z的最短路徑，詳細的解答過程

結構化程序實現的基本原理

結構化程序設計方法

1. 自頂向下

2. 逐步細化

3. 模塊化設計

4. 結構化編碼

結構化程序設計由迪克斯特拉(E.W.dijkstra)在1969年提出，是以模塊化設計為中心，將待開發的軟體系統劃分為若干個相互獨立的模塊，這樣使完成每一個模塊的工作變單純而明確，為設計一些較大的軟體打下了良好的基礎。

　由於模塊相互獨立，因此在設計其中一個模塊時，不會受到其它模塊的牽連，因而可將原來較為複雜的問題化簡為一系列簡單模塊的設計。模塊的獨立性還為擴充已有的系統、建立新系統帶來了不少的方便，因為我們可以充分利用現有的模塊作積木式的擴展。

按照結構化程序設計的觀點，任何演算法功能都可以通過由程序模塊組成的三種基本程序結構的組合: 順序結構、選擇結構和循環結構來實現。

結構化程序設計的基本思想是採用”自頂向下，逐步求精”的程序設計方法和”單入口單出口”的控制結構。自頂向下、逐步求精的程序設計方法從問題本身開始，經過逐步細化，將解決問題的步驟分解為由基本程序結構模塊組成的結構化程序框圖；”單入口單出口”的思想認為一個複雜的程序，如果它僅是由順序、選擇和循環三種基本程序結構通過組合、嵌套構成，那麼這個新構造的程序一定是一個單入口單出口的程序。據此就很容易編寫出結構良好、易於調試的程序來。

缺點：

雖然結構化程序設計方法具有很多的優點，但它仍是一種面向過程的程序設計方法，它把數據和處理數據的過程分離為相互獨立的實體。當數據結構改變時，所有相關的處理過程都要進行相應的修改，每一種相對於老問題的新方法都要帶來額外的開銷，程序的可重用性差。

由於圖形用戶界面的應用，程序運行由順序運行演變為事件驅動，使得軟體使用起來越來越方便，但開發起來卻越來越困難，對這種軟體的功能很難用過程來描述和實現，使用面向過程的方法來開發和維護都將非常困難

普里姆演算法是什麼?

在計算機科學中，普里姆(也稱為Jarník’s)演算法是一種貪婪演算法，它為加權的無向圖找到一個最小生成樹 。

相關簡介：

這意味著它找到邊的一個子集，能夠形成了一個包括所有頂點的樹，其中在樹中所有邊的權重總和最小。該演算法通過從任意起始頂點開始一次給樹增加一個頂點來操作，在每個步驟中添加從樹到另一個頂點的花費最小的可能的連接。

該演算法由捷克數學家沃伊茨奇·賈尼克於1930年開發後，後來在1957年被計算機科學家羅伯特·普里姆，以及在1959年被艾茲赫爾·戴克斯特拉重新發現和重新出版。因此，它有時也被稱為Jarník演算法,普里姆-jarník演算法。普里姆-迪克斯特拉演算法或者DJP演算法。

這個問題的其他眾所周知的演算法包括克魯斯卡爾演算法和 Borvka’s演算法。這些演算法在一個可能的非連通圖中找到最小生成森林；相比之下，普里姆演算法最基本的形式只能在連通圖中找到最小生成樹。然而，為圖中的每個連通分量單獨運行普里姆演算法，也可以用於找到最小生成森林。

就漸近時間複雜度而言，這三種演算法對於稀疏圖來說速度相同，但比其他更複雜的演算法慢。然而，對於足夠密集的圖，普里姆演算法可以在線性時間內運行，滿足或改進其他演算法的時間限制。