[ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點)

前言 : 
在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem). 這裡首先討論單點對全部頂點的最短距離. 

單點對全部頂點 : 
一個頂點到多個頂點通常使用 Dijkstra 演算法求得, 有關Dijkstra 的演算法可以參考 這裡, 下面直接來看例子 : 
請找出下圖頂點5 到各頂點的最短路徑 : 
 

做法相當簡單, 首先由頂點5 開始, 找出頂點5 到各頂點間最小距離, 到達不了以 ∞ 表示. 步驟如下 : 
步驟一 : 
 
D[0]= ∞ , D[1]=12, D[2]= ∞ , D[3]=20, D[4]=14. 在其中找出值最小的頂點, 加入S 集合中 : -> D[1] 
步驟二 : 
 
D[0]= ∞ , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小的頂點D[4] 並加入S集合中 : ->D[1], D[4] 
步驟三 : 
 
D[0]=26 , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小頂點D[2] 並加入S集合 : ->D[1], D[4], D[2] 
步驟四 : 
 
D[0]=26 , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小頂點D[3] 並加入S集合 : ->D[1], D[4], D[2] 
步驟五 : 
加入最後一個頂點及可得到下表. 
 

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4. #define SIZE 7  
5. #define NUMBER 6  
6. #define INFINITE 9999 // 無窮大  
7. int Graph_Matrix[SIZE][SIZE];  // 圖形陣列  
8. int distances[SIZE]; // 路徑長度  
9.   
10. void _BuildGraph_Matrix(int *Path_Cost) {  
11.     int start_Point; // 邊線的起點  
12.     int end_Point; // 邊線的終點  
13.     for(int i=1; i
14.         for(int j=1; j
15.             if(i==j)  
16.                 Graph_Matrix[i][j] = 0; // 對角線為0  
17.             else  
18.                 Graph_Matrix[i][j] = INFINITE;  
19.     // 存入圖形的邊線  
20.     int i=0;  
21.     while(i < SIZE) {  
22.         start_Point = Path_Cost[i*3];  
23.         end_Point = Path_Cost[i*3+1];  
24.         Graph_Matrix[start_Point][end_Point] = Path_Cost[i*3+2];  
25.         i++;  
26.     }  
27. }  
28.   
29. void _PrintGraph_Matrix(){  
30.     for(int i=1; i< SIZE; i++) {  
31.         cout << "Vertx" << i;  
32.         for(int j=1; j
33.             if(Graph_Matrix[i][j] == INFINITE)  
34.                 printf("    x");  
35.             else   
36.                 printf("%5d", Graph_Matrix[i][j]);  
37.         }  
38.         cout << endl;  
39.     }  
40. }  
41.   
42. void _ShortestPath(int vertex, int vertex_total) {  
43.     int shortest_vertex = 1;// 紀錄最短距離的頂點  
44.     int shortest_distance = -1; // 紀錄最短距離  
45.     int goal[SIZE];  // 用來紀錄該頂點是否被選取  
46.     for(int i=1; i<=vertex_total; i++) {  
47.         goal[i] = 0;  
48.         distances[i] = Graph_Matrix[vertex][i];  
49.     }  
50.     goal[vertex] = 1;  
51.     distances[vertex] = 0;  
52.     cout << endl;  
53.     for(int i=1; i<=(vertex_total-1); i++) {  
54.         shortest_distance = INFINITE;  
55.         // 找最短距離  
56.         for(int j=1; j<=vertex_total; j++) {  
57.             if(goal[j]==0 && shortest_distance > distances[j]) {  
58.                 shortest_distance = distances[j];  
59.                 shortest_vertex = j;  
60.             }  
61.         }  
62.         goal[shortest_vertex] = 1;  
63.         // 計算頂點到各頂點的最短距離  
64.         for(int j=1; j<=vertex_total; j++) {  
65.             if(goal[j] == 0 && (distances[j] > distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j])) {  
66.                 distances[j] = distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j];  
67.             }  
68.         }  
69.     }  
70. }  
71.   
72. void ch07_07(bool b) {  
73.     //extern int distance[SIZE]; // 宣告為外部變數  
74.     int Path_Cost[7][3] = {{1,2,10},  
75.                                                {2,3,20},  
76.                                                {2,4,25},  
77.                                                {3,5,18},  
78.                                                {4,5,22},  
79.                                                {4,6,95},  
80.                                                {5,6,77}};  
81.     _BuildGraph_Matrix(&Path_Cost[0][0]);  
82.     cout << "==========================" << endl;  
83.     cout << "此範例圖形相鄰矩陣如下 :" << endl;  
84.     cout << "==========================" << endl;  
85.     cout << "頂點   vex1 vex2 vex3 vex4 vex5 vex6" << endl;  
86.     _PrintGraph_Matrix();  
87.     cout << "==========================" << endl;  
88.     _ShortestPath(1, NUMBER); // 找頂點1 到各頂點最短距離  
89.     cout << "頂點1 到各頂點最短距離為: " << endl;  
90.     cout << "==========================" << endl;  
91.     for(int i=1; i
92.         printf("頂點1 到頂點%2d最短距離=%2d\n", i, distances[i]);  
93.     }  
94. }  

執行結果 : 

==========================
此範例圖形相鄰矩陣如下 :
==========================
頂點 vex1 vex2 vex3 vex4 vex5 vex6
Vertx1 0 10 x x x x
Vertx2 x 0 20 25 x x
Vertx3 x x 0 x 18 x
Vertx4 x x x 0 22 95
Vertx5 x x x x 0 77
Vertx6 x x x x x 0
==========================

頂點1 到各頂點最短距離為:
==========================
頂點1 到頂點 1最短距離= 0
頂點1 到頂點 2最短距離=10
頂點1 到頂點 3最短距離=30
頂點1 到頂點 4最短距離=35
頂點1 到頂點 5最短距離=48
頂點1 到頂點 6最短距離=125

補充說明 : 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (頂點兩兩之間的最短距離)

[ 文章收集 ] Performance Management : What Is Performance Management?

Common Misconceptions : 
What is your definition of performance management? Most people associate it with concepts such as : 

* Appraisal
* Performance-related pay
* Targets and objectives
* Motivation and discipline

Yet, performance management is much more than this. 

A Definition : 
Performance management is about getting results. It is concerned with getting the best from people and helping them to achieve their potential. 
It is an approach to achieving a shared vision of the purpose and aims of the organisation. It is concerned with helping individuals and teams achieve their potential and recognize their role in contributing to the goals of the organisation. 
 

Shifts In Performance Management : 
The approach to performance management has changed over recent years and it is now recognized that enhancing individual and team performance will contribute to bottom-line results : 
 

The Performance Management Toolkit : 
In order to manage both their own performance and that of their team, managers need a toolkit of techniques and skills - 'tools' that work together to help individuals, teams and the organization excel. 
But, like a master craftsman, you need to know how and when to use each of the management tools. All the tools in this tooolbox are covered in follow up discussion. Below is a list of toolkit : 

* Performance Reviews
* Leadership Management Style
* Measuring Performance
* High Performing Teams
* Coaching
* Setting Objectives
* Empowering
* Delegating
* Managing For Performance

The Good Reasons to Get Started : 
If you only want three good reasons for developing your knowledge and approach to performance management, remember it will help to : 

1. Improve individual, team and organization performance.
2. Motivate, develop and release the potential of your people.
3. Enable you to succeed in your role as manager of performance!

Getting to The Heart of The Organization : 
Performance management gets to the very heart of the organization. It needs to reflect and support the organization's culture, strategy and style : 

* What is expected of team
* What they will be rewarded for
* How they should deliver results
* What results the organization is looking for on a business-wide scale?

A Consistent Approach : 
Effective performance management requires a consistent approach to : 

* Leadership
* The way individuals are treated
* The way teams operate
* The performance management system used
* The culture, purpose and strategy of the organization.

Does this the approach your organization take? 

An Inconsistent Approach : 
Inconsistency can lead to problems such as : 

* No clear direction, weak values and weak performance culture.
* Vague and inequitable objectives
* Variable and unfair appraisal/review, leading to a lack of improved performance and motivation
* Inadequate provision for training and development
* Poor communications due to bureaucracy

Or is this the approach your organization takes? 

Case Example1 : 
Proglem : 

Consider a sales organization which recognizes the customer service is vital in maintaining competitive advantage. An extensive customer service training programming completed, yet customer feedback indicates that there has been little improvement.

Reasons : 

This is because targets and incentives were based on volume of sales and not service. People will always focus their efforts on the areas of work for which they are rewarded!!!

Solution : 

The reward system needs to be altered to reflect the emphasis on service. It also needs to recognize the contribution of all members of the team, including back-office support.

Case Example2 : 
Problem : 

Consider the organization which advocates empowerment, passing responsibility down the line, yet fails to achieve this new approach.

Reasons : 

The leadership style at the top of the organization remains autocratic. Mistakes and risk-taking are not tolerated. Employees are not given the skills necessary to adjust successfully to the new approach.

Solutions : 

For it to work, empowerment requires trust from the top, training and coaching, and a different focus for incentives and rewards.

Creating A Sense of Mission : 
For performance management to work well, organizations need to have a clear picture of where they are going. This means communicating their purpose, strategy, the values they adhere to, and the standards of behavior they expect from their employees. If an organization is clear about these issues, it can communicate them to the employees through its performance management systems. 
A well-planned and implemented approach to performance management can achieve this sense of mission by providing : 

* Clarify on the organization's overall goals
* A framework for linking strategies and priorities to jobs
* Greater clarity on role requirements and support to employees
* Recognition of successes and regular feedback.
* A clear basis for promotion.
* A framework for development and improvement.

An organization with a consistent approach to performance management is like a first-class orchestra. A first-class orchestra is well conducted and clear about the symphony it is playing 
The instruments are all in tune and the musicians know their roles and the tempo to follow. They reach a crescendo together and enjoy the process.