Hello from TASTEDEV,
We would like to introduce TASTEREMOTE, a remote desktop project that lets you view and control a remote computer through a web browser. Install the host app on the PC you want to access, then connect from a browser without installing a separate viewer app. You can use the TASTEDEV-operated server or run your own server.
TASTEREMOTE is under active development as we continue to improve its features and stability. Depending on your setup, you may encounter bugs or features that are not yet fully polished. Please review the supported operating systems and known limitations before getting started.
If you run into a problem or have feedback, please leave a comment or question on the product page. Including your operating system, TASTEREMOTE version, and the steps that led to the issue will help us investigate and improve the project.
Product and downloads: https://tastedev.net/products/remote
Documentation: https://tastedev.net/docs/remote
For setup instructions and development updates, follow the development log through the Learn more link below.
There is still work to do, and your feedback will help us improve TASTEREMOTE step by step. Thank you for your interest, for trying the project, and for sharing your experience with us.
The TASTEDEV Team
Guía de Camino mínimo y árbol generador mínimo · 2/6
How it works
Por ahora, este capítulo solo está disponible en inglés.
This chapter traces each algorithm on a small graph so you can see the order of relaxations. The Dijkstra example uses directed edges A→B 4, A→C 1, C→B 2, B→D 1, C→D 5, D→E 3 with source A.
Dijkstra step by step
Dijkstra keeps a min-heap of (distance, vertex) pairs. It repeatedly pops the closest vertex; because all weights are non-negative, no later path can make that vertex any cheaper, so its distance is final. It then relaxes the vertex's outgoing edges. When a distance improves we simply push a new pair instead of updating the old one; outdated pairs are skipped when popped ("lazy deletion").
Pop
A
B
C
D
E
Note
start
0
inf
inf
inf
inf
heap: (0,A)
(0,A)
0
4
1
inf
inf
push (4,B), (1,C)
(1,C)
0
3
1
6
inf
B improves 4 to 3
(3,B)
0
3
1
4
inf
D improves 6 to 4
(4,B)
0
3
1
4
inf
stale, skipped
(4,D)
0
3
1
4
7
push (7,E)
(6,D)
0
3
1
4
7
stale, skipped
(7,E)
0
3
1
4
7
heap empty
Final distances: A 0, B 3, C 1, D 4, E 7. The shortest path to E is A→C→B→D→E.
Why negative edges break Dijkstra
Take A→B 2, A→C 3, C→B -2. Dijkstra settles B at distance 2 before it looks at C, but the true distance is 3 + (-2) = 1. The greedy "closest is final" argument assumes that extending a path never makes it shorter, which is false with negative weights. Use Bellman-Ford instead.
Bellman-Ford
Bellman-Ford relaxes every edge, V - 1 times. A shortest path without cycles has at most V - 1 edges, and after round k every path of k edges has been accounted for. One extra round then acts as a test: if any edge can still be relaxed, a negative cycle is reachable from the source.
from math import inf
def bellman_ford(n, edges, source):
dist = [inf] * n
dist[source] = 0
for _ in range(n - 1):
changed = False
for u, v, w in edges:
if dist[u] != inf and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # early exit: nothing moved this round
break
for u, v, w in edges:
if dist[u] != inf and dist[u] + w < dist[v]:
raise ValueError("negative cycle reachable from source")
return dist
# S=0, A=1, B=2, C=3
print(bellman_ford(4, [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 2)], 0)) # [0, 2, 5, 4]
In round 1 the edges are scanned in the listed order: A becomes 4, B becomes 5, then B→A lowers A to 2, and A→C sets C to 4. Round 2 changes nothing, so the loop stops early.
Floyd-Warshall
Floyd-Warshall computes all pairs at once with a three-level loop. After processing intermediate vertex k, d[i][j] is the shortest path from i to j that uses only vertices 0..k in between. The order of the loops matters: k must be the outermost.
from math import inf
def floyd_warshall(d):
n = len(d)
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return d
d = [[0, 3, inf], [inf, 0, 1], [2, inf, 0]]
print(floyd_warshall(d)) # [[0, 3, 4], [3, 0, 1], [2, 5, 0]]
After the run, a negative value on the diagonal (d[i][i] < 0) means vertex i lies on a negative cycle.
0-1 BFS
When every weight is 0 or 1, a deque replaces the heap. A vertex reached by a 0-edge goes to the front, by a 1-edge to the back, so the deque always stays sorted by distance and each step is O(1).
from collections import deque
from math import inf
def zero_one_bfs(adj, source):
dist = [inf] * len(adj)
dist[source] = 0
dq = deque([source])
while dq:
u = dq.popleft()
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
print(zero_one_bfs([[(1, 1), (2, 0)], [(3, 1)], [(1, 0), (3, 1)], []], 0)) # [0, 0, 0, 1]
Prim from A pops the cheapest edge that leaves the tree: A-B 1, then B-C 2 (cheaper than A-C 3), then C-D 4 (cheaper than B-D 5). Both reach the same tree of weight 7. They can pick different trees only when equal weights allow several MSTs, and the total is always the same.
Summary
Dijkstra settles the closest vertex each time and skips stale heap entries.
Bellman-Ford needs V - 1 rounds; a change in an extra round means a negative cycle.
Floyd-Warshall loops over intermediate vertices k, outermost.
0-1 BFS keeps the deque ordered by pushing 0-edges to the front.
Kruskal works edge by edge, Prim grows a single tree; both are greedy and both are correct.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.