# Weighted graph general concepts
# 加权图一般概念
Every weighted graph should contain:
1. Vertices/Nodes (I will use "vertex" in this readme).
每个加权图应包含：
1. 顶点/节点（我将在本自述文件中使用“顶点”）。
<img src="Images/Vertices.png" height="250" />
2. Edges connecting vertices. Let's add some edges to our graph. For simplicity let's create directed graph for now. Directed means that edge has a direction, i.e. vertex, where it starts and vertex, where it ends. But remember a VERY IMPORTANT thing:
* All undirected graphs can be viewed as a directed graph.
* A directed graph is undirected if and only if every edge is paired with an edge going in the opposite direction.
2. 连接顶点的边缘。 让我们在图中添加一些边。 为简单起见，我们现在创建有向图。 定向意味着边缘有一个方向，即顶点，它开始的位置和顶点，它的终点。 但请记住一件非常重要的事情：
* 所有无向图可以被视为有向图。
* 当且仅当每个边缘与沿相反方向的边缘配对时，有向图是无向的。
<img src="Images/DirectedGraph.png" height="250" />
3. Weights for every edge.
3. 每个边的权重。
<img src="Images/WeightedDirectedGraph.png" height="250" />
Final result.
Directed weighted graph:
最后结果。
定向加权图：
<img src="Images/WeightedDirectedGraphFinal.png" height="250" />
Undirected weighted graph:
<img src="Images/WeightedUndirectedGraph.png" height="250" />
And once again: An undirected graph it is a directed graph with every edge paired with an edge going in the opposite direction. This statement is clear on the image above.
Great! Now we are familiar with general concepts about graphs.
再一次：一个无向图，它是一个有向图，每条边与一条边相反。 这个陈述在上面的图片中很清楚。
大！ 现在我们熟悉关于图的一般概念。
# The Dijkstra's algorithm
This [algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) was invented in 1956 by Edsger W. Dijkstra.
这个[算法](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)由Edsger W. Dijkstra于1956年发明。
It can be used when you have one source vertex and want to find the shortest paths to ALL other vertices in the graph.
The best example is a road network. If you want to find the shortest path from your house to your job or if you want to find the closest store to your house then it is time for the Dijkstra's algorithm.
当您有一个源顶点并且想要找到图中所有其他顶点的最短路径时，可以使用它。
最好的例子是道路网络。 如果你想找到从你家到你工作的最短路径，或者如果你想找到离你家最近的商店，那么现在是Dijkstra算法的时候了。
The algorithm repeats following cycle until all vertices are marked as visited.
Cycle:
1. From the non-visited vertices the algorithm picks a vertex with the shortest path length from the start (if there are more than one vertex with the same shortest path value then algorithm picks any of them)
2. The algorithm marks picked vertex as visited.
3. The algorithm checks all of its neighbours. If the current vertex path length from the start plus an edge weight to a neighbour less than the neighbour current path length from the start than it assigns new path length from the start to the neighbour.
When all vertices are marked as visited, the algorithm's job is done. Now, you can see the shortest path from the start for every vertex by pressing the one you are interested in.
算法重复以下循环，直到所有顶点都标记为已访问。
周期：
1. 从非访问顶点，算法从开始选择具有最短路径长度的顶点（如果有多个具有相同最短路径值的顶点，则算法选择其中任何一个）
2. 该算法将拾取的顶点标记为已访问。
3. 算法检查所有邻居。 如果从开始加上边缘权重到邻居的当前顶点路径长度小于从开始起的邻居当前路径长度，则从开始到邻居分配新的路径长度。
当所有顶点都标记为已访问时，算法的作业就完成了。 现在，您可以按下您感兴趣的那个，从每个顶点开始看到从最开始的最短路径。
I have created **VisualizedDijkstra.playground** game/tutorial to improve your understanding of the algorithm's flow. Besides, below is step by step algorithm's description.
A short sidenote. The Swift Algorithm Club also contains the A* algorithm, which essentially is a faster version of Dijkstra's algorithm for which the only extra prerequisite is you have to know where the destination is located.
我创建了 **VisualizedDijkstra.playground** 游戏/教程，以提高您对算法流程的理解。 此外，下面是逐步算法的描述。
一个简短的旁注。 Swift算法俱乐部还包含 `A*`算法，它本质上是Dijkstra算法的更快版本，唯一的额外先决条件是您必须知道目的地的位置。
## Example
## 例子
Let's imagine that you want to go to the shop. Your house is A vertex and there are 4 possible stores around your house. How to find the closest one/ones? Luckily, you have a graph that connects your house with all these stores. So, you know what to do :)
让我们想象你想去商店。 你的房子是一个顶点，你家周围有4个可能的商店。 如何找到最近的一个/一个？ 幸运的是，你有一个图表，连接你的房子和所有这些商店。 所以，你知道怎么做:)
### Initialisation
### 初始化
When the algorithm starts to work initial graph looks like this:
当算法开始工作时，初始图形如下所示：
<img src="Images/image1.png" height="250" />
The table below represents graph state:
下表表示图形状态：
| | A | B | C | D | E |
|:------------------------- |:---:|:---:|:---:|:---:|:---:|
| Visited | F | F | F | F | F |
| Path Length From Start | inf | inf | inf | inf | inf |
| Path Vertices From Start | [ ] | [ ] | [ ] | [ ] | [ ] |
>inf is equal infinity which basically means that algorithm doesn't know how far away is this vertex from start one.
>F states for False
>T states for True
> inf等于无穷大，这基本上意味着算法不知道这个顶点距离起点有多远。
> F表示False
> T表示True
To initialize our graph we have to set source vertex path length from source vertex to 0 and append itself to path vertices from start.
要初始化我们的图形，我们必须将源顶点路径长度从源顶点设置为0，并将自身附加到从start开始的路径顶点。
| | A | B | C | D | E |
|:------------------------- |:---:|:---:|:---:|:---:|:---:|
| Visited | F | F | F | F | F |
| Path Length From Start | 0 | inf | inf | inf | inf |
| Path Vertices From Start | [A] | [ ] | [ ] | [ ] | [ ] |
Great, now our graph is initialised and we can pass it to the Dijkstra's algorithm, let's start!
Let's follow the algorithm's cycle and pick the first vertex which neighbours we want to check.
All our vertices are not visited but there is only one has the smallest path length from start. It is A. This vertex is the first one which neighbors we will check.
First of all, set this vertex as visited.
太好了，现在我们的图表被初始化了，我们可以将它传递给Dijkstra的算法，让我们开始吧！
让我们按照算法的循环，选择我们要检查的邻居的第一个顶点。
我们没有访问所有顶点，但只有一个顶点从开始开始具有最小的路径长度。 它是A.这个顶点是我们将检查的邻居的第一个顶点。
首先，将此顶点设置为已访问。
A.visited = true
<img src="Images/image2.png" height="250" />
After this step graph has this state:
在此步骤图之后具有以下状态：
|
swift-algorithm-club的翻译。使用Swift学习算法和数据结构。.zip （785个子文件） 
CNAME 20B Graph.entitlements 322B
eurocoins.gif 88KB BuildTree.gif 18KB AnimatedExample.gif 17KB AnimatedExample.gif 9KB standard_deviation.gif 1KB bayes.gif 1KB normal_distribution.gif 925B multinomial.gif 703B mean.gif 590B .gitignore 34B CombineSets.graffle 27KB BuildTree.graffle 13KB DeleteTwoChildren.graffle 11KB FixedSizeArrays.graffle 10KB AnimatedExample.graffle 6KB AnimatedExample.graffle 5KB Compression.graffle 4KB Tree.graffle 4KB Decompression.graffle 4KB Example.graffle 4KB BalanceOK.graffle 4KB AdjacencyMatrix.graffle 3KB Tree.graffle 3KB Traversing.graffle 3KB Array.graffle 3KB TreeAndList.graffle 3KB Example.graffle 3KB BinaryTree.graffle 3KB LargeHeap.graffle 3KB TopologicalSort.graffle 3KB AdjacencyList.graffle 3KB Flights.graffle 3KB Operations.graffle 3KB BalanceNotOK.graffle 2KB DeleteOneChild.graffle 2KB Cycles.graffle 2KB StateMachine.graffle 2KB SocialNetwork.graffle 2KB DeleteLeaf.graffle 2KB Tasks.graffle 2KB Searching.graffle 2KB ParentChildren.graffle 2KB InvalidSort.graffle 2KB FlightsDirected.graffle 2KB HeapShape.graffle 2KB GraphResult.graffle 2KB ChordMap.graffle 2KB MinimumMaximum.graffle 2KB Height.graffle 2KB Graph.graffle 2KB Insert3.graffle 2KB Remove4.graffle 2KB Insert2.graffle 2KB Demo1.graffle 2KB Graph.graffle 2KB Example.graffle 2KB Tree.graffle 2KB Graph.graffle 2KB Algorithms.graffle 2KB MaxHeap.graffle 2KB Remove3.graffle 2KB TraversalTree.graffle 2KB CoreData.graffle 2KB Remove2.graffle 2KB TraversalTree.graffle 2KB SortedArray.graffle 2KB Remove5.graffle 2KB Insert1.graffle 2KB DAG.graffle 2KB Tree2.graffle 2KB Unbalanced.graffle 2KB Remove1.graffle 2KB Balanced.graffle 2KB Tree1.graffle 2KB Heap1.graffle 2KB RegularTree.graffle 2KB
radix_sort.jpg 101KB RotationStep0.jpg 22KB RotationStep2.jpg 13KB RotationStep1.jpg 13KB RotationStep3.jpg 13KB quadratic_formula.jpg 4KB quadratic_equation.jpg 3KB Contents.json 903B Contents.json 62B README.markdown 30KB README.markdown 28KB README.markdown 24KB README.markdown 24KB README_en.markdown 24KB README_en.markdown 24KB README.markdown 23KB README.markdown 21KB README_en.markdown 20KB README_en.markdown 20KB README.markdown 19KB README.markdown 19KB README_en.markdown 19KB共 785 条
- 1
- 2
- 3
- 4
- 5
- 6
- 8
资源评论
