Untitled
unknown
plain_text
3 years ago
3.8 kB
7
Indexable
floyd warshall:::: #include <bits/stdc++.h> using namespace std; #define V 4 #define INF 99999 void printSolution(int dist[][V]); void floydWarshall(int graph[][V]) { int dist[V][V], i, j, k; for (i = 0; i < V; i++) for (j = 0; j < V; j++) dist[i][j] = graph[i][j]; for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) dist[i][j] = dist[i][k] + dist[k][j]; } } } printSolution(dist); } void printSolution(int dist[][V]) { cout << "The following matrix shows the shortest " "distances" " between every pair of vertices \n"; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][j] == INF) cout << "INF" << " "; else cout << dist[i][j] << " "; } cout << endl; } } int main() { int graph[V][V] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } }; floydWarshall(graph); return 0; } Bellmanford ;;;;; #include <bits/stdc++.h> using namespace std; struct Edge { int src, dest, weight; }; struct Graph { int V, E; struct Edge* edge; }; struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph; graph->V = V; graph->E = E; graph->edge = new Edge[E]; return graph; } void printArr(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < n; ++i) printf("%d \t\t %d\n", i, dist[i]); } void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = graph->E; int dist[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int weight = graph->edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } for (int i = 0; i < E; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int weight = graph->edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { printf("Graph contains negative weight cycle"); return; } } printArr(dist, V); return; } int main() { int V = 5; int E = 8; struct Graph* graph = createGraph(V, E); graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = -1; graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 4; graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].weight = 3; graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].weight = 2; graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].weight = 2; graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].weight = 5; graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].weight = 1; graph->edge[7].src = 4; graph->edge[7].dest = 3; graph->edge[7].weight = -3; BellmanFord(graph, 0); return 0; }
Editor is loading...