Multi-Stage Graphs using Dynamic Programming technique.

 

Algorithm:

Algorithm BGraph(G, k, n, p){

bcost[l]:=0.0;

for j:=2 to n do     {

Let r be such that (r, j) is an edge of G and bcost[r] + c[r,j] is minimum; bcost[j]:=bcost[r]+c[r,j];

d[j]:=r;     } p[l]:1; p[k]:=n;

for j:=k— 1 to 2 do p[j]:=d[p[j+1]];}

Source Code:

def shortestDist(graph): global INF

dist = [0] * N path = [None] * N dist[N - 1] = 0

for i in range(N - 2, -1, -1): dist[i] = INF

for j in range(N):

if graph[i][j] == INF: continue

if dist[i] > graph[i][j] + dist[j]: dist[i] = graph[i][j] + dist[j] path[i] = j

shortest_path = [0]

node = 0

while node != N-1:

node = path[node] shortest_path.append(node)

return dist[0], shortest_path

N = 8

INF = 999999999999

graph = [[INF, 1, 2, 5, INF, INF, INF, INF],

[INF, INF, INF, INF, 4, 11, INF, INF],

[INF, INF, INF, INF, 9, 5, 16, INF],

[INF, INF, INF, INF, INF, INF, 2, INF],

[INF, INF, INF, INF, INF, INF, INF, 18],

[INF, INF, INF, INF, INF, INF, INF, 13],

[INF, INF, INF, INF, INF, INF, INF, 2]]

shortest_dist, shortest_path = shortestDist(graph) print("Shortest distance:", shortest_dist) print("Shortest path:", shortest_path[::-1])

Comments

Post a Comment

Popular posts from this blog

2. Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.

Image
 In Cisco Packet Tracer, you can simulate this scenario by configuring access control lists (ACLs) on routers to control the flow of traffic between the networks. Here's a basic example: Procedure  1. **Create the Networks:**    - Place three routers on the workspace and label them R1, R2, and R3.    - Connect the routers as follows:      - Connect R1 to R2 and R3.      - Connect R2 to R3.    - Assign IP addresses to the router interfaces for each network (N1, N2, N3). 2. **Configure Router ACLs:**    - Access the CLI of each router.    For R1 (assuming FastEthernet interfaces):    ```bash    enable    configure terminal    interface FastEthernet0/0    ip address <N1_IP> <Subnet_Mask>    exit    interface FastEthernet0/1    ip address <N2_IP> <Subnet_Mask>    exit    access-li...
Read more

Kruskal algorithm using greedy technique.

Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do       { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then        { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); }                 } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Read more