int [] pred is not initialized properly.
This field currently defaults to 0, which means that the preceding node for all other nodes is set to node 0 on initialization. Which means all nodes with an unreachable predecessor are linked via node 0 in the output, yielding an incorrect path even if there wasn't one.
Negative weights
That's a simple one - it's not supported by Dijkstra's algorithm. Not relevant to your problem though, as negative costs don't occur in a Multicast network. So no need to choose an more expensive algorithm for this edge case.
Using Dijkstra's algorithm for Multicast
While this works, and you did in fact manage to call Dijkstra only once, that's not how Multicast works.
For multicast, you want a minimum spanning tree including all recipients, as you want the minimize the cumulative to all recipients with regard to late package duplication. This yields different results with Dijkstra, as Dijkstra will happily discard expensive edges for one route, even though they are used anyway for another one, effectively requiring both routes to be traversed now and doubling the cumulative costs.
See Use Dijkstra's to find a Minimum Spanning Tree? Use Dijkstra's to find a Minimum Spanning Tree? for an extended discussion as to why that isn't the same.
Be warned that calculating a spanning tree only works for an undirected graph, not a directed one such as yours.
Not supporting costs of 0
This is a bug. A cost of 0 is perfectly valid, both as an input for Dijkstra, and as a cost when finding routes. Think e.g. of routing between local bridges, which has a cost so low, that you can't fit it into the metric.
Choose a different default value for int [][] edges.
Dense versus spare graphs
Your graph is obviously sparse, and will be for the majority of networks you are applying this algorithm to. This means there is no need to store the full matrix, using an array of arrays is perfectly sufficient.
This also reduces int [] neighbors (int vertex) from scanning the table, to simply returning a direct reference on the list of neighbors.
In return this requires resizing the inner array when inserting a new edge, but this is a rare case.
Using a flat array for int [] dist
This has the direct disadvantage that int minVertex (int [] dist, boolean [] v) now needs to perform a full sweep of that array every single time it want's to extract the minimum.
Use a PriorityQueue instead, the added memory overhead is worth it. You don't even need to insert yet unseen nodes into that queue yet.
int [] pred is not initialized properly.
This field currently defaults to 0, which means that the preceding node for all other nodes is set to node 0 on initialization. Which means all nodes with an unreachable predecessor are linked via node 0 in the output, yielding an incorrect path even if there wasn't one.
Negative weights
That's a simple one - it's not supported by Dijkstra's algorithm. Not relevant to your problem though, as negative costs don't occur in a Multicast network. So no need to choose an more expensive algorithm for this edge case.
Using Dijkstra's algorithm for Multicast
While this works, and you did in fact manage to call Dijkstra only once, that's not how Multicast works.
For multicast, you want a minimum spanning tree including all recipients, as you want the minimize the cumulative to all recipients with regard to late package duplication. This yields different results with Dijkstra, as Dijkstra will happily discard expensive edges for one route, even though they are used anyway for another one, effectively requiring both routes to be traversed now and doubling the cumulative costs.
See Use Dijkstra's to find a Minimum Spanning Tree? for an extended discussion as to why that isn't the same.
Be warned that calculating a spanning tree only works for an undirected graph, not a directed one such as yours.
Not supporting costs of 0
This is a bug. A cost of 0 is perfectly valid, both as an input for Dijkstra, and as a cost when finding routes. Think e.g. of routing between local bridges, which has a cost so low, that you can't fit it into the metric.
Choose a different default value for int [][] edges.
Dense versus spare graphs
Your graph is obviously sparse, and will be for the majority of networks you are applying this algorithm to. This means there is no need to store the full matrix, using an array of arrays is perfectly sufficient.
This also reduces int [] neighbors (int vertex) from scanning the table, to simply returning a direct reference on the list of neighbors.
In return this requires resizing the inner array when inserting a new edge, but this is a rare case.
Using a flat array for int [] dist
This has the direct disadvantage that int minVertex (int [] dist, boolean [] v) now needs to perform a full sweep of that array every single time it want's to extract the minimum.
Use a PriorityQueue instead, the added memory overhead is worth it. You don't even need to insert yet unseen nodes into that queue yet.
int [] pred is not initialized properly.
This field currently defaults to 0, which means that the preceding node for all other nodes is set to node 0 on initialization. Which means all nodes with an unreachable predecessor are linked via node 0 in the output, yielding an incorrect path even if there wasn't one.
Negative weights
That's a simple one - it's not supported by Dijkstra's algorithm. Not relevant to your problem though, as negative costs don't occur in a Multicast network. So no need to choose an more expensive algorithm for this edge case.
Using Dijkstra's algorithm for Multicast
While this works, and you did in fact manage to call Dijkstra only once, that's not how Multicast works.
For multicast, you want a minimum spanning tree including all recipients, as you want the minimize the cumulative to all recipients with regard to late package duplication. This yields different results with Dijkstra, as Dijkstra will happily discard expensive edges for one route, even though they are used anyway for another one, effectively requiring both routes to be traversed now and doubling the cumulative costs.
See Use Dijkstra's to find a Minimum Spanning Tree? for an extended discussion as to why that isn't the same.
Be warned that calculating a spanning tree only works for an undirected graph, not a directed one such as yours.
Not supporting costs of 0
This is a bug. A cost of 0 is perfectly valid, both as an input for Dijkstra, and as a cost when finding routes. Think e.g. of routing between local bridges, which has a cost so low, that you can't fit it into the metric.
Choose a different default value for int [][] edges.
Dense versus spare graphs
Your graph is obviously sparse, and will be for the majority of networks you are applying this algorithm to. This means there is no need to store the full matrix, using an array of arrays is perfectly sufficient.
This also reduces int [] neighbors (int vertex) from scanning the table, to simply returning a direct reference on the list of neighbors.
In return this requires resizing the inner array when inserting a new edge, but this is a rare case.
Using a flat array for int [] dist
This has the direct disadvantage that int minVertex (int [] dist, boolean [] v) now needs to perform a full sweep of that array every single time it want's to extract the minimum.
Use a PriorityQueue instead, the added memory overhead is worth it. You don't even need to insert yet unseen nodes into that queue yet.
int [] pred is not initialized properly.
This field currently defaults to 0, which means that the preceding node for all other nodes is set to node 0 on initialization. Which means all nodes with an unreachable predecessor are linked via node 0 in the output, yielding an incorrect path even if there wasn't one.
Negative weights
That's a simple one - it's not supported by Dijkstra's algorithm. Not relevant to your problem though, as negative costs don't occur in a Multicast network. So no need to choose an more expensive algorithm for this edge case.
Using Dijkstra's algorithm for Multicast
While this works, and you did in fact manage to call Dijkstra only once, that's not how Multicast works.
For multicast, you want a minimum spanning tree including all recipients, as you want the minimize the cumulative to all recipients with regard to late package duplication. This yields different results with Dijkstra, as Dijkstra will happily discard expensive edges for one route, even though they are used anyway for another one, effectively requiring both routes to be traversed now and doubling the cumulative costs.
See Use Dijkstra's to find a Minimum Spanning Tree? for an extended discussion as to why that isn't the same.
Be warned that calculating a spanning tree only works for an undirected graph, not a directed one such as yours.
Not supporting costs of 0
This is a bug. A cost of 0 is perfectly valid, both as an input for Dijkstra, and as a cost when finding routes. Think e.g. of routing between local bridges, which has a cost so low, that you can't fit it into the metric.
Choose a different default value for int [][] edges.
Dense versus spare graphs
Your graph is obviously sparse, and will be for the majority of networks you are applying this algorithm to. This means there is no need to store the full matrix, using an array of arrays is perfectly sufficient.
This also reduces int [] neighbors (int vertex) from scanning the table, to simply returning a direct reference on the list of neighbors.
In return this requires resizing the inner array when inserting a new edge, but this is a rare case.
Using a flat array for int [] dist
This has the direct disadvantage that int minVertex (int [] dist, boolean [] v) now needs to perform a full sweep of that array every single time it want's to extract the minimum.
Use a PriorityQueue instead, the added memory overhead is worth it. You don't even need to insert yet unseen nodes into that queue yet.