Comments (3)
Hi @qianzhang42 , thanks for catching that! Would you be interested in contributing a patch (including a test case) for it?
from algos.
Sorry for the late reply. Sure. I would love to patch this. But I am not quite familiar about the whole process. Are there any tutorial or instructions on doing this? Thanks.
from algos.
What you need is the indexed priority queue which can reorganize automatically when its elements are modified. Here is the code
from pqdict import pqdict
def calculate_distances(graph, starting_vertex):
distances = {vertex: float('infinity') for vertex in graph}
distances[starting_vertex] = 0
pq = pqdict({starting_vertex: 0})
while len(pq) > 0:
current_vertex, current_distance = pq.popitem()
for neighbor, neighbor_distance in graph[current_vertex].items():
distance = distances[current_vertex] + neighbor_distance
if distance < distances[neighbor]:
distances[neighbor] = distance
pq[neighbor] = distance
return distances
example_graph = {
'U': {'V': 2, 'W': 5, 'X': 1},
'V': {'U': 2, 'X': 2, 'W': 3},
'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
'Y': {'X': 1, 'W': 1, 'Z': 1},
'Z': {'W': 5, 'Y': 1},
}
print calculate_distances(example_graph, 'X')
from algos.
Related Issues (20)
- Request to talk about how deque is implemented in Python HOT 2
- Representation of empty unordered list feels wrong HOT 1
- Fix code in Prim's Spanning Tree algorithm section
- Add exercises
- Fix unordered list implemenation
- Fix code samples with overflowing content
- Implement a literate JavaScript form HOT 1
- Deploy all branches to S3 or similar HOT 1
- Table of Contents "Introduction" links to incorrect page HOT 2
- Figure out why Alek isn't seeing Inconsolata HOT 2
- Don't use both 1st person singular and plural in book copy HOT 2
- Fix collision of syntax highlighter and markdown converter HOT 1
- Experiment with adding more JS translations of the python source examples HOT 4
- On mobile Safari, pages of book partially loading or not loading at all
- Fix KaTeX subscript formatting
- Clarify list vs array language
- decimal-to-binary.png image is inaccurate HOT 1
- The issue for Shortest Path with Dijkstra’s Algorithm HOT 1
- Typo: "0" is used in place of the big-O
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from algos.